← Back to the Applied Science guide

Learning Theory

Why does a model that fits old data work on new data? Learning theory answers that question. It also tells you when the answer is no.

Every Applied Science loop has a theory moment. Someone asks why your model overfit, or why a huge network did not. They ask why offline gains vanished online. All three are learning theory questions. This page covers the core ideas with real math. Each topic ends with what it means for shipped models and the questions you will hear.

You do not need to prove theorems in the interview. You do need to state them right, know their assumptions, and say where they break. That is the senior bar.

Part A — The Core Setup

1. The learning problem: risk, empirical risk, ERM

The formal setup

• Data. Pairs (x, y) drawn i.i.d. (independent and identically distributed) from an unknown distribution D over X × Y.
• Hypothesis class. A set H of candidate functions h: X → Y. Linear models, trees of depth 6, a ResNet with fixed shape.
• Loss. A function ℓ(h(x), y) ≥ 0 that scores one prediction.
• Sample. A training set S = {(x₁, y₁), …, (x_m, y_m)} of size m.

Two quantities drive everything. The true risk is what we care about. The empirical risk is what we can compute.

True risk:        R(h)  = E(x,y)~D [ ℓ(h(x), y) ]

Empirical risk:   R̂S(h) = (1/m) ∑i=1..m ℓ(h(xi), yi)

ERM:              ĥ = argminh ∈ H R̂S(h)

For any fixed h, the empirical risk is an unbiased estimate of the true risk. So E_S[R̂_S(h)] = R(h). But this breaks for the ERM winner. We picked ĥ because it looked good on S. So R̂_S(ĥ) is biased low. That bias is the heart of overfitting.

Three sources of error

Let h* be the best possible predictor over all functions. This is the Bayes predictor. Let h_H be the best predictor inside H. Then the excess risk of the ERM output splits in two.

R(ĥ) − R(h*) = [ R(hH) − R(h*) ]  +  [ R(ĥ) − R(hH) ]
                approximation error     estimation error

• Approximation error. The cost of the class. A linear model cannot fit a curve. More data does not help.
• Estimation error. The cost of finite data. You picked the wrong member of H because S was noisy. It shrinks with m and grows with the size of H.
• Optimization error. A third term in practice. SGD does not find the exact ERM solution. For deep nets this term is real and sometimes helps.

The key bound for ERM

One short argument links the gap to uniform convergence. Suppose every h in H has |R(h) − R̂_S(h)| ≤ ε. Then ERM is close to the best in class.

R(ĥ) ≤ R̂S(ĥ) + ε        (uniform convergence)
     ≤ R̂S(hH) + ε      (ĥ minimizes empirical risk)
     ≤ R(hH) + 2ε       (uniform convergence again)

So all of classical theory reduces to one job. Bound sup_h |R(h) − R̂_S(h)|. PAC, VC and Rademacher are three ways to do it.

Intuition

Think of a class of 1,000 students who all guess on a 10 question quiz. Someone will score 9 out of 10 by luck. If you hire the top scorer, you hired luck. The more students you test, the higher the luckiest score. A bigger hypothesis class is a bigger class of guessers.

Why it matters in practice

• Hyperparameter search is ERM too. Trying 500 configs on one validation set picks the luckiest one. Its validation score is biased up.
• Feature selection on the full data leaks. Pick features with all rows, then cross-validate, and the CV score lies.
• Leaderboards overfit. Teams that check a shared benchmark many times inflate it. Kaggle private leaderboards exist for this reason.
• Error budgets. When a model stalls, ask which term dominates. High train error is approximation. A big train-test gap is estimation.

Interview check

• Q: Why is training error a biased estimate of test error? A: We chose the model to minimize it. Selection on a noisy score biases that score low.
• Q: Name the error terms in excess risk. A: Approximation, from the class. Estimation, from finite data. In practice also optimization, from imperfect training.
• Q: What does uniform convergence buy you? A: If all hypotheses have small gap at once, ERM lands within 2ε of the best in class.

2. Bias-variance decomposition

Setup

Let y = f(x) + ε, where E[ε] = 0 and Var(ε) = σ². Train a model on a random dataset D. Call the result ĥ_D. Define the average model over all training sets as h̄(x) = E_D[ĥ_D(x)]. Fix a test point x. The noise ε at x is independent of D.

Derivation for squared loss

Write the error as a sum of two pieces. Then expand.

ED,ε[ (y − ĥD(x))2 ]
  = E[ (f(x) + ε − ĥD(x))2 ]
  = E[ε2] + 2 E[ε] E[f(x) − ĥD(x)] + E[ (f(x) − ĥD(x))2 ]
  = σ2 + 0 + ED[ (f(x) − ĥD(x))2 ]

Now add and subtract h̄(x) inside the last term:

ED[ (f − h̄ + h̄ − ĥD)2 ]
  = (f − h̄)2 + 2 (f − h̄) ED[h̄ − ĥD] + ED[ (ĥD − h̄)2 ]
  = (f − h̄)2 + 0 + VarD(ĥD(x))

Result:
E[(y − ĥD(x))2] = σ2  +  (f(x) − h̄(x))2  +  VarD(ĥD(x))
                     noise        bias2             variance

Both cross terms die for the same reason. One factor is a constant and the other has mean zero. The first uses E[ε] = 0 and independence. The second uses E_D[ĥ_D] = h̄ by definition. Average over x to get the full test error.

A runnable check

This demo fits polynomials of several degrees to 500 fresh datasets. It then measures bias and variance directly.

import numpy as np

rng = np.random.default_rng(0)
f = lambda x: np.sin(2 * np.pi * x)          # true function
sigma, n, trials = 0.3, 30, 500
x_test = np.linspace(0.05, 0.95, 200)

for degree in [1, 3, 5, 7]:
    preds = np.empty((trials, x_test.size))
    for t in range(trials):
        x = rng.uniform(0, 1, n)
        y = f(x) + sigma * rng.standard_normal(n)
        coef = np.polyfit(x, y, degree)
        preds[t] = np.polyval(coef, x_test)
    mean_pred = preds.mean(axis=0)
    bias2 = np.mean((mean_pred - f(x_test)) ** 2)
    var = np.mean(preds.var(axis=0))
    print(f"degree {degree:2d}: bias^2={bias2:.3f}  var={var:.3f}  "
          f"expected test MSE={bias2 + var + sigma**2:.3f}")

# degree  1: bias^2=0.152  var=0.021  expected test MSE=0.263
# degree  3: bias^2=0.003  var=0.013  expected test MSE=0.106
# degree  5: bias^2=0.000  var=0.026  expected test MSE=0.117
# degree  7: bias^2=0.001  var=0.380  expected test MSE=0.471

Degree 1 is all bias. Degree 7 is all variance. Degree 3 wins. Note the noise floor of 0.09 sits under every row.

Intuition

Picture a dartboard. Bias is how far the center of your throws sits from the bull's-eye. Variance is how spread out the throws are. A rigid model throws tight but off center. A flexible model centers well but scatters.

Why it matters in practice

• Ensembles cut variance. Bagging averages B models. With pairwise correlation ρ, variance drops to ρσ² + (1 − ρ)σ²/B. Random forests add feature sampling to lower ρ.
• Boosting cuts bias. Each round fits what the last rounds missed. That is why boosting uses shallow trees.
• Diagnosing a stalled model. High train error means bias. Add features or capacity. A large gap means variance. Add data or regularization.
• Noise sets the floor. Label noise in click data caps achievable log loss. No model beats σ².

Interview check

• Q: Derive the decomposition. A: Write y − ĥ as noise plus (f − h̄) plus (h̄ − ĥ). Square it. Both cross terms have a zero-mean factor and vanish.
• Q: Does more data reduce bias? A: Not for a fixed class. It reduces variance. Bias falls only if you also grow the class.
• Q: Why does bagging help trees but not linear regression much? A: Deep trees have high variance and low bias. OLS is already a stable, low-variance estimator.

3. Generalization gap and train, validation, test logic

The math of a held-out estimate

The test set works because the model is fixed before we look. Then the test losses are i.i.d. with mean R(h). For a loss in [0, 1], Hoeffding's inequality bounds the error of the estimate.

P( |R̂test(h) − R(h)| > ε ) ≤ 2 exp(−2 ntest ε2)

With probability 1 − δ:  |R̂test(h) − R(h)| ≤ √( ln(2/δ) / (2 ntest) )

With 10,000 test points and δ = 0.05, the error is at most 0.0136. That holds for one model. Pick the best of k models on the same set and the bound needs ln(2k/δ). That is the union bound from Section 4.

Why three splits

• Train. Fits the parameters. Its error is biased low by the full power of the class.
• Validation. Picks hyperparameters, features, early stopping. It is a small ERM over configs. So its error is biased low too, but less.
• Test. Used once at the end. It is the only unbiased number. Reuse it and it becomes a validation set.

Cross-validation

K-fold CV trains K models, each on (K−1)/K of the data. It averages the held-out errors. It uses data well but has two subtle points.

• It estimates the error of the training procedure, not of one fitted model.
• The folds share training data. So fold errors are correlated. The naive standard error is too small. Bengio and Grandvalet (2004) showed no unbiased variance estimator exists for K-fold CV.
• Nested CV is needed when CV both tunes and reports. The inner loop tunes. The outer loop reports.

When i.i.d. splits lie

Random splits assume test data comes from the same D. Production data rarely does. Pick a split that mirrors deployment.

• Time split. Train on the past, test on the future. Required for ads, feeds, fraud and forecasting.
• Group split. Keep all rows of a user, session or document in one fold. Otherwise the model memorizes the user.
• Leakage check. Any feature computed after the label time leaks. Aggregates over the full table leak too.

Why it matters in practice

• Offline-online gaps. A random split on click logs leaks future behavior. The model looks great offline and flat in the A/B test.
• Adaptive data analysis. Teams that tune on the same eval set for months overfit it. Refresh holdouts or use a reusable holdout scheme.
• Small eval sets. A 0.2% AUC gain on 5,000 rows is inside noise. Report a bootstrap CI.
• Early stopping uses validation. So the stopping epoch is a hyperparameter. Do not report the same set as test.

Interview check

• Q: Why can you not tune on the test set? A: Tuning is selection. Selection biases the chosen score up. The test set then stops being unbiased.
• Q: How big must a test set be for ±1% accuracy at 95%? A: Hoeffding gives n ≥ ln(40)/(2 · 0.01²) ≈ 18,400. The normal approximation at p = 0.5 gives about 9,600.
• Q: When is a random split wrong? A: When data has time order or groups. Use time or group splits that match how the model is used.

Part B — Bounding the Gap

4. PAC learning and sample complexity for finite classes

The definition

A class H is PAC learnable if a learner exists with this property. For every ε, δ in (0, 1) and every distribution D, given m ≥ m_H(ε, δ) samples, it outputs ĥ with:

PS~Dm( R(ĥ) ≤ minh∈H R(h) + ε ) ≥ 1 − δ

• ε is the accuracy. That is the "approximately".
• δ is the failure chance. That is the "probably". A bad sample can always fool you.
• The bound must hold for every D. That makes PAC a worst case theory.
• The realizable case assumes some h in H has zero error. The agnostic case drops that.

Two tools

Hoeffding's inequality. For i.i.d. Z_i in [0, 1] with mean μ:

P( |(1/m) ∑ Zi − μ| > ε ) ≤ 2 exp(−2 m ε2)

Union bound. P(A₁ or … or A_k) ≤ ∑ P(A_j). It needs no independence.

Derivation: agnostic finite class

Let the loss lie in [0, 1]. Call h "bad" if its empirical risk is more than ε from its true risk.

P( ∃ h ∈ H : |R̂S(h) − R(h)| > ε )
   ≤ ∑h∈H P( |R̂S(h) − R(h)| > ε )     (union bound)
   ≤ |H| · 2 exp(−2 m ε2)                    (Hoeffding)

Set the right side to δ and solve:

  m ≥ ( ln|H| + ln(2/δ) ) / (2 ε2)

Equivalently, with probability ≥ 1 − δ, for ALL h ∈ H at once:

  R(h) ≤ R̂S(h) + √( (ln|H| + ln(2/δ)) / (2m) )

This gives uniform convergence at level ε. By the argument in Section 1, ERM is then within 2ε of the best in class.

Derivation: realizable finite class

Now assume some h in H has zero true error. ERM returns a consistent h, one with zero training error. We bound the chance that a bad h with R(h) > ε stays consistent.

P( one bad h fits all m points ) ≤ (1 − ε)m ≤ e−εm

P( any bad h is consistent ) ≤ |H| e−εm ≤ δ

  m ≥ ( ln|H| + ln(1/δ) ) / ε

Realizable needs 1/ε samples. Agnostic needs 1/ε². The gap comes from variance. With zero error the estimate has no noise near zero. With nonzero error it does.

A worked number

A model has d = 100 parameters stored as 32-bit floats. Then |H| ≤ 2³²⁰⁰, so ln|H| ≈ 2,218. For ε = 0.05 and δ = 0.01 in the agnostic case:

m ≥ (2218 + ln 200) / (2 · 0.0025) = (2218 + 5.3) / 0.005 ≈ 444,700

This "discretization trick" shows a key point. Even a continuous class has effective size near 2^{bits × params}. So sample complexity scales with parameter count times precision. That is crude, and VC dimension makes it sharper.

Why it matters in practice

• Model selection over k candidates. Picking the best of k on a validation set of size n costs √(ln k / n) of optimism. Use that to size validation sets.
• Rules and lookup models. Small rule sets, decision lists and shallow trees are finite classes. The bound is often tight enough to use directly.
• Labeling budgets. The 1/ε² law means each halving of error needs 4 times the labels. Plan annotation spend with it.
• Multiple testing in experiments. The same union bound is Bonferroni. Testing 20 metrics at α = 0.05 needs α/20 each.

Interview check

• Q: Derive sample complexity for a finite class. A: Hoeffding per hypothesis, union bound over |H|, set to δ. Get m ≥ (ln|H| + ln(2/δ))/(2ε²).
• Q: Why 1/ε in the realizable case but 1/ε² agnostic? A: A consistent bad hypothesis must survive m independent chances to fail. That decays as e^−εm. Agnostic estimates have variance near ε(1−ε), which needs 1/ε².
• Q: Is the union bound tight? A: No. Similar hypotheses fail on the same samples. VC and Rademacher bounds exploit that overlap.

5. VC dimension and what it says

Definitions

• Dichotomy. One labeling of m points that some h in H produces.
• Growth function. Π_H(m) is the most dichotomies H can make on any m points. It is at most 2^m.
• Shattering. H shatters a set if it realizes all 2^m labelings of it.
• VC dimension. The size of the largest set H can shatter. Write it d_VC.

Common values

• Halfspaces in R^d with a bias. d_VC = d + 1.
• Intervals on the line. d_VC = 2.
• Axis-aligned rectangles in R². d_VC = 4.
• sin(θx) thresholded. d_VC = ∞ with one parameter. Parameter count is not capacity.
• ReLU nets with W weights and L layers. Θ(W L log W), from Bartlett et al. (2019).

Sauer's lemma and the VC bound

The magic step is Sauer's lemma. Once m passes d, the growth function turns from exponential to polynomial.

ΠH(m) ≤ ∑i=0..d C(m, i) ≤ (e m / d)d       for m ≥ d

VC generalization bound (with probability ≥ 1 − δ, for all h ∈ H):

R(h) ≤ R̂S(h) + O( √( ( d log(m/d) + log(1/δ) ) / m ) )

Sample complexity:
  agnostic:    m = Θ( (d + log(1/δ)) / ε2 )
  realizable:  m = Θ( (d + log(1/δ)) / ε )    (ERM pays an extra log(1/ε))

The proof swaps the infinite class for its finite set of behaviors on a double sample. That is the symmetrization trick. Then it applies the finite class bound with |H| replaced by Π_H(2m). So ln|H| becomes about d log m.

The fundamental theorem

For binary classification with 0-1 loss, these are equivalent. H has finite VC dimension. H has uniform convergence. ERM is a PAC learner. H is PAC learnable. So finite VC dimension is exactly the condition for learnability in this setting.

What it does and does not say

• It says capacity, not parameter count, controls the gap. It says you need data roughly linear in d_VC.
• It says the bound is distribution free. It holds for the worst D.
• It does not explain deep nets. A ResNet has d_VC in the millions and trains on fewer samples. The bound is vacuous, above 1, yet the net generalizes.
• It does not see the data or the algorithm. Real data is far from worst case. SGD does not explore all of H.

Why it matters in practice

• The rule of thumb. Ten examples per effective degree of freedom comes from this line of thought. It is a heuristic, but a useful one for linear and tree models.
• Margin beats dimension. SVMs with margin γ on data of radius R have capacity near R²/γ², free of input dimension. That is why kernel SVMs work in huge feature spaces.
• Explaining deep learning honestly. Say VC bounds are vacuous for big nets. Then point to norm, margin, compression and PAC-Bayes bounds instead.

Interview check

• Q: VC dimension of linear classifiers in R^d? A: d + 1 with a bias term. Any d+1 points in general position are shattered. Radon's theorem rules out d+2.
• Q: Can one parameter give infinite VC dimension? A: Yes. sign(sin(θx)) shatters arbitrarily large point sets with a suitable θ.
• Q: Why don't VC bounds explain deep learning? A: They are worst case over H and D. Big nets can fit random labels, so any bound based only on H is vacuous.

6. Rademacher complexity

Definition

Draw σ₁, …, σ_m as independent random signs, each ±1 with probability 1/2. These are Rademacher variables. For a class F of real functions and a fixed sample S:

Empirical:  R̂S(F) = Eσ[ supf∈F (1/m) ∑i=1..m σi f(xi) ]

Expected:   ℜm(F) = ES[ R̂S(F) ]

The sum is the correlation between f and random labels. The sup picks the f that matches the noise best. If the class can match any sign pattern, the value is near 1. If it can only fit smooth trends, it is near 0.

The bound

Let the loss class be G = {(x, y) → ℓ(h(x), y) : h ∈ H} with values in [0, 1]. Then with probability at least 1 − δ, for all h in H:

R(h) ≤ R̂S(h) + 2 ℜm(G) + √( ln(1/δ) / (2m) )

Data-dependent version:
R(h) ≤ R̂S(h) + 2 R̂S(G) + 3 √( ln(2/δ) / (2m) )

The proof has two steps. McDiarmid's inequality shows the worst-case gap concentrates near its mean. Then symmetrization bounds that mean by twice the Rademacher complexity.

Useful facts

• Contraction (Talagrand). If the loss is L-Lipschitz in the prediction, then ℜ(ℓ ∘ H) ≤ L ℜ(H). So you can bound the model class and ignore the loss.
• Linear class with norm limit. For {x → w·x : ||w||₂ ≤ B} and ||x||₂ ≤ X, R̂_S ≤ BX/√m. No dimension appears.
• Finite class. Massart's lemma gives ℜ ≤ √(2 ln|H| / m). This recovers the PAC bound.
• Link to VC. For binary classes, ℜ_m ≤ √(2 d ln(em/d) / m).

Intuition

VC dimension asks if the class can fit every labeling of some worst set of points. Rademacher asks how well it fits random labelings of your points, on average. It is data dependent and measures fit, not just yes or no. That makes it tighter and lets it see norms and margins.

Why it matters in practice

• Norms are the real capacity. The BX/√m bound explains why weight decay and feature scaling matter more than raw dimension.
• A cheap sanity test. Train your pipeline on shuffled labels. If validation stays above chance, you have leakage.
• Margin-based bounds for nets. Spectral-norm bounds (Bartlett, Foster, Telgarsky 2017) build on this. They track generalization better than parameter count.

Interview check

• Q: Explain Rademacher complexity in one sentence. A: The expected best correlation between a function in the class and random ±1 labels on the sample.
• Q: Why is it better than VC dimension? A: It depends on the actual data and handles real-valued classes. It also captures norm limits that VC ignores.
• Q: What does fitting random labels tell you? A: The class has near-maximal Rademacher complexity. So uniform convergence over that class cannot explain the observed generalization.

Part C — Controlling Capacity

7. Regularization as capacity control and as a Bayesian prior

The capacity view

Regularized ERM solves a penalized problem. By Lagrange duality, it matches a constrained problem for some radius B.

minw  R̂S(w) + λ Ω(w)      ⇔      minw R̂S(w)  subject to  Ω(w) ≤ B

For a linear model with ||w||₂ ≤ B, Section 6 gave a gap of order BX/√m. So λ directly sets the capacity. Larger λ means smaller B, more bias and less variance. This is structural risk minimization (Vapnik). You pick the class size that minimizes a bound on test error.

The Bayesian view

Assume Gaussian noise y = w·x + ε with ε ~ N(0, σ²). Put a prior on the weights. Then the MAP estimate is a penalized fit.

Prior:      w ~ N(0, τ2 I)
Posterior:  p(w | S) ∝ exp( −||y − Xw||2 / (2σ2) ) · exp( −||w||2 / (2τ2) )

−log posterior = ||y − Xw||2 / (2σ2) + ||w||2 / (2τ2) + const

Multiply by 2σ2:   ||y − Xw||2 + (σ2/τ2) ||w||2      ⇒   ridge with λ = σ2/τ2

Laplace prior p(wj) ∝ exp(−|wj|/b)        ⇒   lasso with λ = 2σ2/b

The ratio σ²/τ² reads well. Noisy data or a tight prior means strong regularization. MAP is still a point estimate. Full Bayes would average over the posterior and give uncertainty too.

What ridge does to each direction

Take the SVD X = U D V^T with singular values d_j. Ridge has a closed form and a clean reading.

ŵridge = (XTX + λI)−1 XT y

X ŵridge = ∑j uj · [ dj2 / (dj2 + λ) ] · ujT y

Effective degrees of freedom:   df(λ) = ∑j dj2 / (dj2 + λ)

• Strong directions with large d_j pass nearly untouched.
• Weak directions with small d_j shrink toward zero. Those are the noisy, high-variance ones.
• df(λ) falls from p at λ = 0 to 0 as λ grows. It is a smooth count of parameters.
• Hoerl and Kennard (1970) proved some λ > 0 always beats OLS in mean squared error.

Lasso versus ridge

• Geometry. The L1 ball has corners on the axes. The loss contours often touch a corner. So lasso sets weights to exactly zero.
• Prior. Laplace has a sharp peak at zero and heavy tails. It believes most weights are zero and a few are large.
• Correlated features. Lasso picks one at random. Ridge spreads weight across them. Elastic net mixes both.

Regularizers that do not look like penalties

• Early stopping. Run gradient descent on least squares from zero. After t steps of size For gradient descent on least squares from zero, after t steps of size η, each direction is scaledeta;, each direction is scaled by 1 − (1 − ηd_j²)^t. That behaves like ridge with λ ≈ 1/(ηt).
• Dropout. For generalized linear models it is close to an adaptive L2 penalty (Wager et al. 2013). It also discourages co-adapted units.
• Data augmentation. It encodes invariances as a prior. A flipped cat is still a cat.
• Label smoothing. It caps logit size and adds a prior toward the uniform label.
• Weight decay in Adam. L2 in the loss and decoupled weight decay differ under adaptive optimizers. AdamW uses the decoupled form.

Why it matters in practice

• Sparse ID features. Ads and recsys models have billions of rare IDs. Strong L2 or L1 on embeddings keeps rare IDs near the prior.
• Tuning λ is tuning capacity. Sweep it on a log scale on validation data. The best value moves with data size.
• Bayesian reading for priors. Shrink a new market's model toward the global model. That is a prior centered on the global weights, not on zero.
• Explaining choices. Saying "L1 because we expect few active features" shows you know the prior behind the penalty.

Interview check

• Q: Show ridge is MAP. A: Gaussian likelihood times Gaussian prior. Take the negative log. You get squared error plus (σ²/τ²)||w||².
• Q: Why does lasso give exact zeros and ridge not? A: The L1 penalty has a kink at zero. Its subgradient lets a weight stay at zero while the loss gradient is small.
• Q: How is early stopping a regularizer? A: Gradient descent fits strong directions first. Stopping early leaves weak, noisy directions near zero, like ridge.

8. No free lunch and inductive bias

Two forms of the theorem

Wolpert (1996). Average over all target functions on a finite domain, uniformly. Then every learner has the same expected error on points outside the training set. That error is chance.

The PAC form (Shalev-Shwartz and Ben-David). Let A be any learner for binary labels with 0-1 loss. Let m < |X|/2. Then a distribution D exists with two properties.

• Some function f has R_D(f) = 0. So the problem is easy for the right class.
• With probability at least 1/7 over the sample, R_D(A(S)) ≥ 1/8.

So the class of all functions is not PAC learnable on an infinite domain. You must restrict H. That restriction is a prior choice made before you see data.

Why it is true

Training data says nothing about unseen points unless you assume a link. If every labeling of the unseen points is equally likely, any guess is a coin flip. Learning needs a reason to believe nearby points share labels, or that the world is smooth, or sparse.

Inductive biases you use every day

• Linear models. Effects add up and scale. Good for well-made features.
• Trees and GBDTs. Axis-aligned splits and interactions. Strong on tabular data with mixed scales.
• k-NN and kernels. Nearby points have similar labels. The kernel defines "nearby".
• CNNs. Locality and translation equivariance. Weight sharing bakes this in.
• Transformers. Weak bias, content-based mixing. They need more data but scale further.

Why it matters in practice

• Baselines matter. A GBDT often beats a deep net on tabular data. Its bias fits the problem better.
• Data versus bias. Weak biases need more data. With little data, pick a model with stronger assumptions.
• Feature design is bias design. A log transform encodes "ratios matter". A cyclic hour feature encodes "midnight is near 11 PM".
• Benchmarks do not transfer for free. A method that wins on ImageNet may lose on your logs. Test on your own distribution.

Interview check

• Q: Does no free lunch mean ML cannot work? A: No. It means learning needs assumptions. Real problems have structure, and good models match it.
• Q: What is the inductive bias of a CNN? A: Local features and translation equivariance, through small kernels and weight sharing. Pooling adds some invariance.
• Q: When would you choose a strong-bias model? A: When data is small or noisy, or when you know the structure. Strong bias trades variance for bias.

Part D — Modern Generalization

9. Double descent and why big nets generalize

The curve

Let p be the number of parameters and n the number of samples. The interpolation threshold is near p = n. That is where the model can first fit the training set exactly.

Why the peak happens

Take least squares with random features Φ of shape n × p. Past the threshold, many weight vectors fit the data exactly. Take the minimum-norm one, β̂ = Φ⁺y, using the pseudoinverse.

• At p ≈ n, the system is square. Exactly one fit exists. The smallest singular value of Φ is near zero.
• Noise gets divided by that tiny singular value. So ||β̂|| explodes and test error spikes.
• As p grows past n, there are many exact fits. The smallest singular value grows again. The min-norm fit spreads weight across many features and stays smooth.

import numpy as np

rng = np.random.default_rng(1)
n, d, sigma = 40, 5, 0.2
X = rng.standard_normal((n, d));   Xt = rng.standard_normal((2000, d))
w = rng.standard_normal(d)
y = np.sin(X @ w) + sigma * rng.standard_normal(n)
yt = np.sin(Xt @ w)

W = rng.standard_normal((d, 1000)) / np.sqrt(d)   # fixed random first layer
relu = lambda z: np.maximum(z, 0)

for p in [5, 20, 35, 40, 45, 60, 100, 300, 1000]:
    Phi, Phit = relu(X @ W[:, :p]), relu(Xt @ W[:, :p])
    beta = np.linalg.pinv(Phi) @ y            # min-norm least squares
    test = np.mean((Phit @ beta - yt) ** 2)
    print(f"features p={p:4d}  test MSE={test:8.3f}  ||beta||={np.linalg.norm(beta):8.2f}")

# features p=  35  test MSE=   1.330  ||beta||=   14.35
# features p=  40  test MSE= 629.267  ||beta||=  341.87   <- p = n, the spike
# features p=  45  test MSE=   2.117  ||beta||=   10.45
# features p= 300  test MSE=   0.912  ||beta||=    1.85
# features p=1000  test MSE=   0.850  ||beta||=    0.98

Watch the norm column. Test error tracks the norm of the solution, not the parameter count. That is the whole story in one line.

Implicit regularization of gradient descent

Nobody calls a pseudoinverse on a neural net. So why would training pick a "small" solution? Because the optimizer has a built-in preference.

• Least squares. Gradient descent from w₀ = 0 only moves in the row space of X. So it converges to the minimum-norm interpolator. No penalty was written down.
• Logistic regression on separable data. The weights grow without limit. But their direction converges to the hard-margin SVM solution (Soudry et al. 2018). The rate is slow, about 1/log t.
• SGD noise. Minibatch noise scales with η/B, the learning rate over the batch size. It shakes the weights out of sharp minima. Flat minima tend to generalize better, and PAC-Bayes bounds make that precise.
• Architecture. Many nets behave close to their linearization early in training. This is the neural tangent kernel view. They then act like a kernel method with min-norm bias.

Benign overfitting

A model can fit noisy labels perfectly and still predict well. Bartlett, Long, Lugosi and Tsigler (2020) showed when this happens for min-norm linear regression.

• The data covariance needs a few strong directions that carry the signal.
• It also needs many weak directions. Their count must be large relative to n.
• The noise gets absorbed by those weak directions. Each takes a tiny share, so no single spike hurts predictions.
• With too few weak directions, the noise concentrates and the overfit is harmful.

Other forms of double descent

• Epoch-wise. Test error can fall, rise, then fall again over training time (Nakkiran et al. 2019).
• Sample-wise. Near the threshold, more data can hurt. Adding samples moves n toward p.
• Regularization removes the peak. Tuned ridge flattens the spike. The peak is a sign of too little regularization at the threshold.

Why it matters in practice

• Scale with care near the threshold. If a mid-size model does worse than a small one, try a bigger one or more regularization.
• Train to zero loss is fine. Big nets that hit zero training loss can still improve on validation. Do not stop early by reflex.
• Optimizer settings are regularizers. Changing batch size or learning rate changes generalization, not just speed. Retune them together.
• Scaling laws. Test loss in large models falls as a power law in parameters and data. That empirical rule now guides compute budgets more than any bound.

Interview check

• Q: Why does test error peak at p = n? A: Only one exact fit exists. The smallest singular value is near zero, so noise blows up the weight norm.
• Q: What is the implicit bias of gradient descent? A: On least squares from zero, the min-norm solution. On separable logistic data, the max-margin direction.
• Q: When is overfitting benign? A: When many low-variance directions can soak up the noise. Then the interpolating fit stays close to the signal.

10. Distribution shift theory

Three kinds of shift

Write the joint as a product two ways. Each kind of shift holds one factor fixed. Let p be source (train) and q be target (test).

• Covariate shift. q(x) ≠ p(x) but q(y|x) = p(y|x). The inputs move. The rule linking them to labels does not. Example: a new country with different user ages.
• Label shift (prior shift). q(y) ≠ p(y) but q(x|y) = p(x|y). Class rates move. Each class looks the same. Example: flu season raises the share of flu cases.
• Concept shift. q(y|x) ≠ p(y|x). The meaning of the label changes. Example: spammers change tactics, or a policy redefines "harmful".

Importance weighting for covariate shift

The target risk is an expectation under q. Rewrite it as one under p, which is where we have data.

Rq(h) = Ex~q Ey|x [ ℓ(h(x), y) ]
      = Ex~p [ (q(x)/p(x)) · Ey|x ℓ(h(x), y) ]     (needs p(x) > 0 wherever q(x) > 0)

Weighted ERM:   minh  (1/m) ∑i w(xi) ℓ(h(xi), yi),     w(x) = q(x)/p(x)

The step works only because y|x is the same in both. You rarely know the densities. So estimate the ratio with a domain classifier.

Train c(x) ≈ P(target | x) on pooled source and target inputs.

w(x) = q(x)/p(x) = [ c(x) / (1 − c(x)) ] · (nsource / ntarget)

Effective sample size:  ESS = (∑ wi)2 / ∑ wi2

• Weights fix bias but add variance. A few huge weights can dominate.
• Clip or temper the weights. Using w^α with α < 1 trades some bias back for lower variance.
• If the model is well specified, reweighting barely matters. It matters most for misspecified models, which fit the wrong region well.
• If the target has regions with no source support, no weighting can help.

import numpy as np

rng = np.random.default_rng(2)
f = lambda x: np.sin(x)
# Source: x ~ N(0, 1). Target: x ~ N(1.5, 0.5^2). Same p(y|x).
xs = rng.normal(0, 1, 5000)
ys = f(xs) + 0.1 * rng.standard_normal(xs.size)
xt = rng.normal(1.5, 0.5, 5000)
yt = f(xt) + 0.1 * rng.standard_normal(xt.size)

def pdf(x, m, s):
    return np.exp(-0.5 * ((x - m) / s) ** 2) / (s * np.sqrt(2 * np.pi))

w = pdf(xs, 1.5, 0.5) / pdf(xs, 0, 1)        # importance weights q(x)/p(x)

def fit_line(x, y, sw):
    A = np.c_[np.ones_like(x), x] * np.sqrt(sw)[:, None]
    return np.linalg.lstsq(A, y * np.sqrt(sw), rcond=None)[0]

for name, sw in [("unweighted", np.ones_like(xs)), ("importance-weighted", w)]:
    b = fit_line(xs, ys, sw)
    mse = np.mean((b[0] + b[1] * xt - yt) ** 2)
    print(f"{name:20s} target MSE = {mse:.4f}")
ess = w.sum() ** 2 / (w ** 2).sum()
print(f"effective sample size = {ess:.0f} of {xs.size}")

# unweighted           target MSE = 0.1127
# importance-weighted  target MSE = 0.0332
# effective sample size = 925 of 5000

A line cannot fit a sine wave everywhere. So the model is misspecified. Weighting tells it to fit the region the target cares about. Target error drops by about 70%. The price is an effective sample of 925 out of 5,000.

Label shift

Here the fix acts on classes, not inputs. If p(x|y) is fixed, Bayes' rule gives a direct correction.

q(y | x) ∝ p(y | x) · q(y) / p(y)

In logit space:  logitq(y | x) = logitp(y | x) + log( q(y) / p(y) )

You need q(y), the new class rates. Target labels are missing, so estimate them.

• BBSE (black box shift estimation, Lipton et al. 2018). Let C be the confusion matrix on source validation, with C_ij = p(ŷ = i, y = j). Let μ̂ be the predicted label rates on target. Solve C w = μ̂ for w_y = q(y)/p(y).
• EM (Saerens et al. 2002). Alternate between adjusting posteriors and re-estimating priors. It needs calibrated probabilities.

Concept shift

No reweighting helps, because the labeling rule itself changed. Old labels are now partly wrong.

• Get fresh labels from the new regime. Weight recent data more.
• Retrain often, or learn online.
• Monitor calibration and per-segment error, not just input drift. Concept shift can occur with no change in p(x).

A bound for domain adaptation

Ben-David et al. (2010) bound target error by three terms.

RT(h) ≤ RS(h) + ½ dHΔH(S, T) + λ*

λ* = minh∈H [ RS(h) + RT(h) ]

• The first term is source error. You control it.
• The second is how well the class can tell the domains apart. Domain-adversarial training (DANN) tries to shrink it.
• The third is the error of the best joint model. If no single model works on both, adaptation is hopeless.

Why it matters in practice

• Launches and new markets. A model trained on US data shifts in covariates for Brazil. Domain classifier AUC tells you how far.
• Feedback loops. A ranking model shapes what users see. Next week's training data comes from its own choices. That is a policy-induced shift.
• Calibration after a prior change. If the base click rate halves, add log(q/p) to the logit. Do not retrain from scratch.
• Drift monitoring. Track feature drift (PSI, KL), prediction drift, and label-based metrics. Each catches a different kind of shift.

Interview check

• Q: Covariate shift versus concept shift? A: Covariate shift moves p(x) with p(y|x) fixed. Concept shift changes p(y|x). Only the first is fixed by reweighting.
• Q: How do you get importance weights without densities? A: Train a classifier to tell source from target. Its odds, times the size ratio, estimate q(x)/p(x).
• Q: What can go wrong with importance weighting? A: High variance from large weights. No help where source has no support. Bad weights from a poorly calibrated domain classifier.

11. Loss functions and their properties

What each regression loss estimates

The population minimizer of a loss is the target the model chases. For regression the answer is clean.

• Squared loss (y − f)². Minimizer is the conditional mean E[y|x]. Sensitive to outliers.
• Absolute loss |y − f|. Minimizer is the conditional median. Robust, but has a kink at zero.
• Pinball loss at level τ. Minimizer is the τ-quantile. Used for prediction intervals and delivery time estimates.
• Huber loss. Squared near zero, linear in the tails. A mean that resists outliers.

Proper scoring rules

A scoring rule S(q, y) scores a predicted distribution q against the outcome y. Lower is better here. It is proper if reporting the truth is optimal.

Proper:           Ey~p[ S(p, y) ] ≤ Ey~p[ S(q, y) ]   for all q
Strictly proper:  equality only when q = p

Check two common rules in the binary case. Let p = P(y = 1) and q be the prediction.

Log loss:     L(q) = −p log q − (1−p) log(1−q)
              dL/dq = −p/q + (1−p)/(1−q) = 0   ⇒   q = p      (strictly proper)

Brier score:  L(q) = p (1−q)2 + (1−p) q2
              dL/dq = 2(q − p) = 0                  ⇒   q = p      (strictly proper)

• Both reward calibrated probabilities. That is why they train and evaluate CTR models.
• Log loss punishes confident mistakes without limit. A prediction of 0.001 on a positive costs 6.9 nats.
• Brier is bounded. It is gentler on rare confident errors.
• Accuracy and AUC are not proper scoring rules. AUC ignores calibration entirely.

Surrogate losses for classification

We want low 0-1 error. But 0-1 loss is not convex and has zero gradient almost everywhere. So we minimize a convex surrogate φ of the margin z = y f(x), with y in {−1, +1}.

Hinge versus log versus focal

Hinge loss. φ(z) = max(0, 1 − z). Used by SVMs.

• Zero loss and zero gradient once z ≥ 1. Only points near the boundary matter. Those are the support vectors.
• Its Bayes minimizer is f*(x) = sign(2η(x) − 1), where η(x) = P(y = 1 | x). It recovers the class but not the probability.
• So hinge is not proper. SVM scores need Platt scaling before use as probabilities.

Log loss (logistic, cross-entropy). φ(z) = log(1 + e^−z).

• Its Bayes minimizer is f*(x) = log(η/(1 − η)), the true log odds. So σ(f) recovers η. It is strictly proper.
• The gradient in f has size σ(−z). It never hits zero, so confident points still pull a little. This drives the max-margin bias from Section 9.
• It is the negative log likelihood of a Bernoulli model. So it ties ML training to MLE.

Focal loss (Lin et al. 2017). FL(p_t) = −(1 − p_t)^γ log p_t, where p_t is the probability given to the true class.

• The factor (1 − p_t)^γ shrinks the loss on easy, well classified examples. Training time goes to hard ones.
• It was built for dense object detection. There, easy background boxes outnumber objects by about 1000 to 1.
• It is not proper for γ > 0. At true p = 0.9 and γ = 2, the focal-optimal output is about 0.69. It pulls outputs toward 0.5.
• That pull can offset the overconfidence of deep nets. But if you need probabilities, recalibrate on held-out data.

Exponential loss. φ(z) = e^−z. AdaBoost minimizes it. Its minimizer is half the log odds. It grows fast for negative margins, so label noise hurts it badly.

When is a surrogate safe?

Bartlett, Jordan and McAuliffe (2006) answered this. A surrogate is classification-calibrated if minimizing it also minimizes 0-1 risk. For convex φ there is a simple test.

Convex φ is classification-calibrated  ⇔  φ is differentiable at 0 and φ'(0) < 0

Excess risk transfer:   ψ( R0-1(f) − R*0-1 ) ≤ Rφ(f) − R*φ
                        hinge: ψ(θ) = |θ|        log loss: ψ(θ) ≥ θ2/2

Hinge, log, exponential and squared hinge all pass. So driving surrogate risk to its minimum drives 0-1 risk to its minimum. Hinge transfers linearly. Log loss transfers through a square root, which is weaker for classification but buys probabilities.

Why it matters in practice

• Ads ranking needs calibration. Auctions multiply bid by pCTR. A miscalibrated pCTR misprices every ad. Train with log loss and track normalized entropy and calibration ratio.
• Class imbalance. Focal or weighted log loss helps rare classes. Both distort probabilities, so recalibrate before thresholding or pricing.
• Match the loss to the decision. Delivery ETAs want a quantile, not a mean. Revenue forecasts may want a mean. Pick the loss whose minimizer is the number the business uses.
• Evaluation metrics. AUC can rise while log loss worsens. Report both when probabilities feed a downstream system.

Interview check

• Q: Why is log loss proper and hinge loss not? A: Log loss is minimized at the true log odds. Hinge is minimized at sign(2η − 1), which throws away the size of η.
• Q: What does focal loss do to calibration? A: Its minimizer pulls toward 0.5, so outputs are underconfident. Recalibrate with temperature or isotonic scaling if probabilities matter.
• Q: Why use a surrogate at all? A: 0-1 loss is non-convex with zero gradient almost everywhere. A classification-calibrated convex surrogate is tractable and still consistent for 0-1 risk.