MIT 6.7960 Deep Learning — Lec 06. Generalization Theory

Overview

The lecture revisits key concepts of approximation, empirical risk, and population risk, then discusses how deep neural networks generalize despite classical theory limitations. It highlights the importance of data diversity, inductive bias, and ongoing research questions that will shape the field in coming years. This segment examines whether deep learning models, especially large language models, primarily memorize training data or genuinely learn to generalize. Using simple analogies like a filing cabinet, the lecture contrasts memorization with smooth interpolation and explores how model performance on unseen data reflects true generalization. It also encourages practical experiments to quantify memorization versus generalization in modern neural networks. This section explores whether modern language models merely memorize training data or truly generalize. Using combinatorial counting, filing cabinet analogies, and toy experiments with fruit names and text‑to‑image generation, the lecture demonstrates how model performance on unseen sequences can reveal the scale of memorization versus abstraction. The lecturer also highlights a practical project to systematically estimate the number of unique concepts encoded by such models.

Chapter breakdown

Key points

• 00:30Deep neural networks generalize to some degree, and the lecture explores why.
• 05:32Generalization is quantified as the gap between training error and test error.
• 08:42Generalization error is the difference between empirical risk (training error) and population risk (true error).
• 13:07Modern large models (LLMs) trained on billions of data points raise the question: are they merely memorizing an enormous filing cabinet or learning to generalize?
• 16:17A toy experiment with 30 fruit names and 10‑word sequences shows the model can achieve a 100% success rate, implying a very large effective filing cabinet size.
• 20:57Model works on hand‑drawn cats, which were never part of the training set, showing out‑of‑distribution generalization.
• 22:23Explains that ConvNets factorize the image into patches, leading to compositionality and allowing the model to handle new compositions.
• 28:12Kolmogorov complexity is the theoretical gold standard for measuring hypothesis simplicity, but finding the shortest program is computationally intractable.
• 31:06In polynomial regression, low degree models underfit, moderate degrees fit the true function, but very high degrees overfit by modeling noise.
• 35:18Polynomial regression has a closed‑form solution, guaranteeing the same result each run, unlike neural networks where randomness in initialization and mini‑batches leads to different solutions.
• 39:04After passing the interpolation threshold, many solutions that fit the training data exist; implicit regularizers (e.g., smoothness) bias the optimization toward the simplest among them.
• 49:24Assumptions: no noise in the training data, the true function is in the set, and the model randomly picks one of the purple points that fit the training data.
• 52:58A generalization bound states that population risk is bounded by a term proportional to sqrt(d/n), so a larger VC dimension worsens the bound.
• 56:40Experiments with shuffled labels show neural nets achieve 100% training accuracy but poor test accuracy, highlighting the need for better generalization understanding.
• 58:51Empirical observations show that deep nets cannot simply memorize all training data; counting arguments imply they learn representations that generalize to unseen inputs.
• 04:08Empirical probability plots show most random settings fall into the low-complexity region; only a few produce highly uncompressible functions.
• 05:44Even linear deep networks (no nonlinearities) produce block‑structured, low‑rank kernels, indicating that depth alone can encourage better clustering.
• 01:11:39Randomly sampling parameters of a depth‑16 network shows a higher probability of mapping to low‑rank embeddings, illustrating architectural bias.
• 01:14:43Fixed‑step gradient descent favors flat minima—wide, low‑loss basins—over sharp, narrow wells, and flat minima are believed to generalize better.
• 00:20Combining data fitting with structural constraints—like drug–receptor interaction rules—enables models to generalize to new viewpoints or unseen chemical compounds.

Key terms

• Generalization — The ability of a model to perform accurately on unseen data.
• Empirical Risk — Average loss measured on the training data, also called training error.
• Population Risk — Expected loss over the true data-generating distribution, representing test performance.
• Hypothesis Space — The set of all functions/models considered during learning.
• inductive bias — Prior assumptions or preferences a learning algorithm has that guide it toward certain solutions over others.
• Overfitting — A modeling error where a model captures noise in the training data, leading to poor generalization on unseen data.
• Backpropagation — Algorithm to compute gradients for training neural networks via the chain rule.
• Optimization — Process of finding model parameters that minimize a loss function.
• Generalization Error — The difference between the model’s error on training data (empirical risk) and its error on unseen data (population risk).
• Approximation Error — The error made by a model in fitting the true underlying function on the training set.
• Filing Cabinet Model — A memorization strategy where each training input is stored with its correct output; the model returns the stored output if the input is seen again, otherwise predicts a default (often zero).
• Memorization — The act of storing and recalling training data exactly, without learning an underlying pattern.
• Language Model — A neural network trained to predict or generate text based on preceding words.
• Vocabulary — The set of all distinct tokens (words) a model can recognize or generate.
• Sequence Length (n) — The number of tokens in an input sequence fed to a model.
• Combinatorics — Mathematical study of counting arrangements and combinations.
• Filing Cabinet Analogy — A conceptual tool that likens memorization to storing each training example as a separate file.
• Non‑Zero Prediction — Any model output that is not empty or null, indicating the model has made a prediction.
• Generalization Theory — Framework explaining how a model performs on unseen data drawn from the same distribution.
• Edge Detector (HED) — A computer vision technique that highlights edges in images, often used to simulate human sketches.
• Generative Model — A model capable of producing new data instances similar to its training data.
• Image‑to‑Image Mapping — Transforming one type of image (e.g., sketch) into another (e.g., photo) using a neural network.
• Convolutional Net — A neural network architecture that processes inputs by applying convolutional filters, treating each spatial patch independently.
• compositionality — The ability of an architecture to build complex outputs by combining simpler learned components, as seen in language models.
• Permutation Invariance — A symmetry where the output remains unchanged when input elements are reordered.
• equivariance — A property where transformations of the input lead to predictable transformations of the output, e.g., translation in convolutional layers.
• Occam's Razor — The principle that, among models that explain the data equally well, the simplest should be chosen.
• Out‑of‑Distribution — Data points that lie outside the distribution of the training set.
• Architectural Constraints — Design choices in a model that enforce certain symmetries or inductive biases.
• Shortest Program — In algorithmic information theory, the program of minimal length that reproduces the data, often linked to the best predictive model.
• Kolmogorov complexity — The length of the shortest program that outputs a given string; a theoretical measure of data simplicity.
• Bias‑variance tradeoff — The balance between a model’s ability to fit training data (bias) and its sensitivity to training fluctuations (variance).
• Universal approximation — Theoretical guarantee that sufficiently wide neural networks can approximate any continuous function.
• Double descent — A phenomenon where test error first decreases, then increases with model capacity, and decreases again when capacity surpasses the interpolation threshold.
• polynomial regression — A regression model that fits a polynomial function to the data, typically solved with a closed‑form solution.
• closed‑form solution — An analytical expression that gives the exact optimum of a problem without iterative approximation.
• stochastic optimization — An optimization method that uses random subsets (mini‑batches) of data to update model parameters.
• implicit regularizer — A property of the optimization algorithm or architecture that biases solutions toward simpler patterns without explicit penalty terms.
• interpolation threshold — The point at which a model has just enough capacity to fit all training data perfectly.
• overfit — A situation where a model captures noise in the training data, leading to poor generalization.
• Candidate function — A potential model from the hypothesis space that could explain the training data.
• Spurious fit — A hypothesis that matches the training data but does not capture the underlying true pattern.
• Capacity — The size or expressive power of a model class, often measured by the number of functions it can represent.
• VC dimension — A measure of the capacity of a hypothesis class; not the primary factor explaining why random weights produce simple functions.
• Dichotomy — A binary labeling of a set of points, assigning each point either +1 or -1.
• Generalization bound — A theoretical guarantee that limits the difference between training error and expected (population) error, often expressed in terms of the VC dimension and sample size.
• Gradient descent — An optimization algorithm that iteratively adjusts model parameters in the direction that reduces the loss, often leading to particular solutions among many that fit the data.
• VC theory — A theoretical framework that uses VC dimension to bound a model’s capacity and its ability to generalize.
• version space — The set of all hypotheses in a hypothesis space that are consistent with (i.e., fit) the training data.
• parameter function map — The mapping from a model’s parameter vector to the function it represents; many parameter vectors may map to the same function.
• simplicity bias — The tendency of a learning algorithm to favor simpler, smoother functions among many that fit the data.
• filing cabinet — A metaphor for memorizing every training example without learning any underlying pattern.
• Lempel‑Ziv complexity — A measure of the compressibility of a sequence, used here to evaluate the complexity of functions represented by neural networks.
• Kernel matrix — A matrix of pairwise similarities between data points in the representation space of a network.
• Rank of a matrix — The number of linearly independent rows or columns; low rank indicates a clustered, simplified structure.
• Deep linear net — A neural network composed only of linear transformations, equivalent to a single linear mapping.
• Random matrix theory — A field studying the properties of matrices with randomly drawn entries, including the tendency of matrix products to be low rank.
• effective rank — A measure of how spread out or clustered a matrix’s singular values are; lower effective rank indicates a simpler, less clustered representation.
• implicit bias — The tendency of an optimization algorithm (e.g., SGD) to converge to particular kinds of solutions, such as low‑norm or flat minima, without explicit regularization.
• weight decay — An optimization technique that shrinks weights toward zero during training, encouraging simpler, lower‑norm solutions.
• flat minima — Wide, low‑loss regions in parameter space that are robust to perturbations and are associated with better generalization.
• invariance — A property where a model’s output remains unchanged under specific transformations of its input, such as channel pooling.
• symmetry — Architectural design that embeds invariance or equivariance, enabling models to generalize across transformed inputs.
• NeRF model — Neural Radiance Fields, a neural architecture that renders 3D scenes by learning volume density and color from 2D images.
• domain knowledge — Specialized information or constraints from a particular field that can be integrated into a learning model.
• structural constraints — Rules or equations derived from known physical, chemical, or biological properties that restrict a model’s behavior.
• finite model — A computational model with a bounded number of parameters or operations.

← All MIT OpenCourseWare course notes