Statistical Learning and Generalization

A team tries 1,000 prompts against the same 40 support cases and celebrates the 92% winner. Its score might describe a better prompt. It might also describe the luckiest fit to those particular 40 cases. The score is real; its meaning isn't settled.

Validation and Leakage separated fitting from honest measurement. Now the search itself can fit the benchmark. Statistical learning theory explains how many candidates, how much data, and which test boundary are needed before an unseen-data claim is credible.^{[1]Reference 1Statistical Learning Theoryhttps://web.stanford.edu/class/cs229t/2016/notes.pdf}

Start with one predictor and one loss

Start with 40 reviewed cases: 36 routes are correct and 4 fail. We need one number for what happened in this sample, then a separate quantity for fresh cases.

Assign loss 0 to a correct route and loss 1 to an incorrect one. The average loss is its empirical risk:

$$\widehat L(h)=\frac{1}{n}\sum_{i=1}^{n}\ell(h(x_i),y_i)$$

Here $h$ is one predictor, $x_i$ is a case, $y_i$ is its reviewed label, and $n$ is the number of cases. Population risk $L(h)=E[\ell(h(X),Y)]$ averages over fresh cases from the intended population instead.

Four failures among 40 cases give empirical risk $4/40=0.10$. That number is exact for these rows. It isn't a proof that future failure probability equals 0.10.

Training can drive this sample average down. Generalization asks whether the same predictor keeps its loss low on cases it hasn't seen.

Use the sample size, failures, and delta=0.05 to put a conservative radius beside the observed risk. The output keeps the measurement and its upper endpoint separate.

The router's observed risk is 0.100 and its fixed-predictor Hoeffding radius is 0.215. Does 0.315 describe its measured future failure rate?

Answer

No. The measured quantity is 0.100 on the observed sample. Adding 0.215 produces a conservative upper-risk bound under the stated independence, bounded-loss, fixed-model, and failure-probability assumptions; it isn't an observed population failure rate.

Bound one fixed predictor before searching

The code gave us a number, not its justification. A concentration inequality controls how far an observed average can drift from its expectation. For independent losses bounded between zero and one, Hoeffding's inequality gives:^{[1]Reference 1Statistical Learning Theoryhttps://web.stanford.edu/class/cs229t/2016/notes.pdf}

$$P\left(\left|\widehat L(h)-L(h)\right|\ge t\right)\le2e^{-2nt^2}$$

Choosing failure probability $\delta$ and solving for $t$ gives:

$$t=\sqrt{\frac{\log(2/\delta)}{2n}}$$

The word fixed matters: the predictor must be chosen independently of the sample used in the bound. Losses must also be bounded, and observations must be independent and representative. Forty retries of one case aren't forty independent case draws.

Why can't a fixed-predictor bound automatically certify the best of 1,000 prompts tried on the same sample?

Answer

The winning prompt was selected after seeing those outcomes. Searching 1,000 candidates creates additional opportunities for a lucky sample fit, so the analysis must account for model selection or use untouched evaluation data.

Pay for the hypotheses you searched

One fixed-model bound no longer answers a search question. For a finite hypothesis class $\mathcal H$ fixed independently of the evaluation sample, a union bound controls every candidate simultaneously:

$$P\left(\exists h\in\mathcal H:\left|\widehat L(h)-L(h)\right|\ge t\right)\le2|\mathcal H|e^{-2nt^2}$$

Rearranging gives a uniform radius:

$$t=\sqrt{\frac{\log(2|\mathcal H|/\delta)}{2n}}$$

The $\log |\mathcal H|$ term is the price of searching multiple candidates in that prespecified class. It describes a conservative guarantee, not the winner's exact optimism.

If researchers rewrite prompts after inspecting the same labels, the candidate class itself depends on those labels. Counting only the 1,000 prompts they eventually tried doesn't automatically restore this fixed-class guarantee.

Before running the comparison, predict what happens when the search grows from 1 to 1,000 candidates while the 40 cases stay fixed.

The bound widens as the search grows. If it becomes too wide to support the desired decision, gather more independent data or reserve a genuinely untouched evaluation set. The calculation prices search; it doesn't tell you whether any candidate is useful.

Two teams both report 1,000 candidate prompts. One declared all prompts before seeing validation labels; the other created each prompt after inspecting earlier validation mistakes. Does the same finite-class bound automatically cover both searches?

Answer

Only the prespecified hypothesis class satisfies the displayed independence assumption directly. Adaptive prompt creation makes the candidate class depend on the evaluation labels, so counting the 1,000 saved prompts doesn't restore the same guarantee. The adaptive winner needs untouched evaluation evidence or a valid adaptive analysis.

Understand capacity beyond a finite candidate count

The preceding bound establishes uniform convergence across one finite hypothesis class. A trainable model usually has continuously many parameter choices, so simply counting attempted configurations isn't always sufficient. We need a way to describe what patterns the whole class can express.

Vapnik-Chervonenkis (VC) dimension asks how many points a binary hypothesis class can label in every possible pattern. A right-facing threshold $h_t(x)=1[x\ge t]$ can assign either label to one point.

For ordered points 2 and 5, however, it can produce (0,0), (0,1), and (1,1), but never (1,0). The class shatters one point rather than two, so its VC dimension is one.

The table makes the capacity limit visible: this class can express only three of the four labelings on two ordered points. A richer class can express more patterns, but that flexibility cuts both ways.

Suppose we refit the same router on several fresh training samples. A high-bias class makes the same systematic mistake because it can't express the rule. A high-variance class changes its fitted rule sharply when the sample changes. Capacity is the set of patterns a class can express, so model selection isn't a contest for the lowest training loss.

Regularization adds a cost for complexity, such as a penalty on large weights. The learner may accept a little more training loss to reduce sensitivity to sample noise, trading some bias for lower variance. Choose that strength with validation evidence, then keep final evaluation separate.

The familiar U-shaped story isn't universal. In some modern settings where a model fits every training row exactly, test error rises near that interpolation point and falls again as capacity grows. Belkin et al. call this pattern double descent and report evidence across model classes and datasets. Treat it as a curve to measure across capacity and training choices, not as permission to assume that a larger model will generalize.

Probably approximately correct (PAC) learning separates the tolerated population error $\varepsilon$ from the allowed guarantee failure probability $\delta$. A PAC-style claim says that, under its sampling and hypothesis assumptions, a learning procedure returns a sufficiently accurate predictor with probability at least $1-\delta$. It doesn't promise every future batch has identical accuracy or that a changed deployment population obeys the original training distribution.^{[1]Reference 1Statistical Learning Theoryhttps://web.stanford.edu/class/cs229t/2016/notes.pdf}

Count the sample needed for a claim

Sample complexity asks how many independent examples a stated guarantee requires. Solve the same bound for sample size:

$$n\ge\frac{\log(2|\mathcal H|/\delta)}{2t^2}$$

At $\delta=0.05$, searching 1,000 candidates and requesting a uniform error radius of 0.05 requires at least 2,120 independent bounded-loss examples under this conservative analysis. An independent final test can evaluate a single frozen winner with a smaller fixed-model requirement because the test didn't participate in selection.

Round the required sample size upward so a fractional case never weakens the guarantee. Before running the cell, predict whether tightening the radius from the earlier 0.215 to 0.05 should require more or fewer cases.

The assumptions matter more than the arithmetic. Group related cases and freeze the final candidate before test evaluation.

Record how many prompts, thresholds, or hyperparameters were tried. Adaptive prompt search can create selection bias beyond what a count of the final candidates captures, so an untouched final test is particularly important.

Distinguish theoretical bounds from deployment guarantees

A bound speaks about a specified sampling process. Before reading the table, ask what changed between the evaluation sample and the traffic where the router will run.

Large neural networks often need capacity measures richer than the size of a finite candidate list. The finite-class calculation still teaches the essential failure: the more opportunities a researcher has to select a flattering result, the more carefully the evidence must be isolated.

Read disagreements between splits as symptoms. Low training loss with high held-out loss points toward overfitting or selection leakage. High loss on both suggests that the class, features, or labels can't express the task. Good held-out loss followed by poor traffic performance points toward distribution shift or a mismatched target. These clues narrow the search; they don't prove a cause.

Build a release-gate worksheet for the 40 reviewed cases. Record the four observed failures, the fixed-predictor radius of 0.215, the 1,000-candidate prespecified-search radius of 0.364, and the resulting conservative upper risks of 0.315 and 0.464.

Then calculate the 2,120 independent examples required for a 0.05 uniform radius. Mark whether candidate prompts were declared before label access, identify repeated underlying tasks, and name the untouched dataset that will evaluate the frozen winner. Reject a worksheet that treats adaptive search or correlated retries as independent fixed-model evidence.