What if the learner leaves the training span?
In high-dimensional linear regression, the training span, every weighted sum of the training inputs, can contain a predictor that predicts fresh examples well while fitting training examples worse than predicting zero. The Core Story shows this tradeoff.
Some algorithms leave the training span: Adam, LASSO, or even stochastic gradient descent (SGD) from random nonzero initialization. Could leaving the span evade the tradeoff?
No. For a global linear predictor, when no direction of the hidden signal is favored in advance, leaving the span cannot improve the average test error across the worlds that could have produced the training data. The learner chooses one coefficient vector after training, before fresh queries. An off-span guess bets on that world; projection removes that bet without changing training predictions. Projection locates the search; scale stays open. Compare the interpolator and best in span on the magnified predictor ray below; the stylized model explains the cost of their different scales.
Put on our information-theory hats: what could any linear learner know? Write the span as S = span{x⃗1, …, x⃗n}. We construct different worlds producing the same training transcript. A world specifies the true spike, the hidden direction the label depends on, and every nuisance vector, the part of each input the label ignores. A transcript is everything the learner receives: D = (X, y). Observed inputs are columns of X, and y lists their labels. We begin with the stylized geometry: fixed lengths and perfectly orthogonal nuisance vectors.
Identical transcripts force a deterministic learner to return the same predictor; a randomized learner must use the same output distribution.
Can two very different truths really produce the same example?
Yes. We rotate the picture so the one observed training vector is horizontal. Then we decompose that same vector in two different ways: gold is signal, blue is nuisance, and in each decomposition the two parts are exactly orthogonal.
Fixed observation: x₁ = (41, 0). Horizontal: training direction s. Vertical: hidden direction h. The two possible signal directions are nearly opposite: ⟨θ₊, θ₋⟩ ≈ −0.904.
Does the ambiguity survive more than one observation?
Yes. More observations rule out some worlds, but as long as some input directions remain untouched by any observation, they need not pin down the spike. With two observations, even a four-dimensional slice of the 1,601-dimensional model leaves an entire circle of compatible truths.
Each candidate world also sets the fresh exam: Gaussian inputs have independent coordinates, with variance 81 along that world’s spike and variance 1 perpendicular to it. The label is the spike coordinate divided by 9.
The marked minimum-norm interpolator fits both observed labels exactly.
Why the magnified strip? The samples and predictors live at very different scales. The upper panel shows the samples; the lower strip zooms in on the predictor ray, from u_int,s = 1/sqrt(881) ~= 0.034 to the best-in-span endpoint u*_s ~= 0.327.
Where do √881 and 20√2 come from? Each example is 9 along the spike plus 40 of its own orthogonal nuisance, so ‖x_i‖² = 1681 and ⟨x_1, x_2⟩ = 81. Along s each has coordinate sqrt((1681+81)/2) = sqrt(881); along q, ±sqrt((1681−81)/2) = ±20sqrt(2).
Why not move along q as well? The two labels agree, but the q-coordinates have opposite signs. Adding bq to a predictor on the s-axis adds 800b^2 to training loss and b^2 to test error in every compatible world. It makes both errors worse. That is why the span frontier follows s alone. On the frontier, improving one error worsens the other. A “dominated” predictor has an alternative with no larger error on either score and a smaller error on at least one.
The animation hides only the s-coordinate, which never changes. In the full four-dimensional picture, each moving gold-plus-blue decomposition still lands on the same fixed sample: 9θ⃗(φ) + 40z⃗i(φ) = x⃗i, i = 1, 2.
x⃗1 fixed⟨θ⃗(φ),x⃗1⟩/9 = 1x⃗2 fixed⟨θ⃗(φ),x⃗2⟩/9 = 1Could a learner exploit one of those unresolved directions?
It can certainly add a vector h perpendicular to the span, h in S-perp. Training loss will not object.
But that silence is exactly the problem: training loss cannot justify adding h either. One compatible world may reward that bet while another, equally compatible, points the other way.
Want to choose before you know the world?
Starting from the span interpolator, choose a purple off-span bet and lock it. A fresh world will be drawn at random from this compatible circle only after you commit.
Each world’s test error already averages over fresh inputs in that world. The circle average then averages those errors over all worlds on the ring.
The hollow dashed marker is the selected world’s equally likely mirror. Across the two worlds, the bet’s signed effects cancel; its squared cost remains.
XTu⃗ = XTPXu⃗
LD(u⃗) = LD(PXu⃗)
L_D is the mean squared training error on the observed data D.
Each training prediction is an inner product ⟨u, xᵢ⟩, and xᵢ lies in the span, so the part of u outside the span contributes nothing to it. u and its span projection PXu therefore make exactly the same training predictions. Adding h changes the learner’s claim about unseen directions, but not one training residual.
Why do the colors change? The exact n = 2 test-error calculation
Each color on the ring shows how the off-span bet changes test error in that particular world: green means lower error than the span interpolator; rust means higher error. Write h for the added vector perpendicular to the training span. The first formula scores one world; the second averages the change over the whole drawn circle.
The visible spike length is a = ‖P_Xθ‖ = 9/√881; the remaining hidden length is √(1−a²).
Can any linear learner beat the span?
The ring uses the interpolator. This panel uses the selected span predictor below. Both share the same off-span bet: projecting here removes it from both. Its luck changes with the reference predictor; its average cost does not.
So far we averaged only around the circle we can draw, using two hidden directions. The original model has 1599 hidden directions: that circle is just a slice. On the full compatible sphere a fixed bet is usually almost perpendicular to the hidden truth, so a nonzero bet has a smaller, still positive average penalty. With no off-span bet, both penalties are zero.
For the same nonzero bet, the circle-average penalty is about 36 times the full-sphere penalty here. By default, the plot below uses the full-sphere average; the predictor and its training predictions stay the same.
X^T u = X^T P_X u
M_D(P_X u) <= M_D(u)
M_D means the largest test risk among worlds compatible with the observed data D.
Keep the training predictions
The span component determines every training prediction. Adding or removing the off-span bet changes the test result at the same training coordinate. Use Project away h to compare the two predictors.
Inspect one compatible world
Drag the gold truth around the inset and inspect the live result. A favorable direction can help some bets; an unfavorable direction reverses that advantage. A zero bet changes nothing. To see a bet that helps in no world, choose Best in span, then Largest bet. A lucky bet from the interpolator can win in one revealed world; it cannot justify an unknown-world guarantee.
Average away directional luck
The observations do not identify the hidden direction. Over the full compatible sphere, directional luck cancels and the squared off-span cost remains. Projecting away the bet never raises the worst-compatible risk either.
Squared off-span cost:
Here B_D is average test error across compatible worlds; a = ‖P_Xθ‖ = 9/√881 is the spike’s projection length, and d − n = 1599 counts directions outside the training span; d = 1601 is the input dimension and n = 2 is the number of examples.
Could the input density reveal which world we are in?
The projection payoff used rotational symmetry in the stylized model. With iid Gaussian inputs, the observed locations can favor some candidate worlds over others. The symmetry we need is smaller: each world and its reflection across the training span still have equal likelihood.
Consider a smaller Gaussian example with spike strength gamma = 2 and candidate signal directions theta+/- = (1, +/-1)/sqrt(2). Suppose we observe x1 = (2, 0). The gold arrows show the candidates; each blue outer contour passes through that same black observation.
For a larger iid training set, keep the spike strengths and target coefficients fixed, and reflect only a candidate frame, the set of spike directions, across the realized training span. The reflection fixes every observed input. It also reflects the Gaussian covariance, so its determinant and each input’s Mahalanobis distance are unchanged. So every individual training point’s density factor is unchanged, as is their product; every label is unchanged too. A rotation-invariant prior gives each frame and its mirror equal posterior weight.
Pair each frame with its equally likely mirror: in their average, opposite off-span effects cancel while the squared cost remains. Both stay compatible with the data, so the worst case is at least their average. Projection keeps every training prediction and never worsens the average or the worst case.
Why does reflection preserve every Gaussian density?
For several spikes, let U be their orthonormal frame, Gamma the diagonal matrix of their fixed strengths, and P_X the projector onto the observed training span. Reflect across that span:
The original covariance is Sigma_U = I + U(Gamma − I)U^T. The reflected world uses J_X U. Its covariance is Sigma_{J_X U} = J_X Sigma_U J_X. Because J_X is orthogonal and fixes each x_i, both the determinant and the Gaussian quadratic form agree:
Hence f_{J_X U}(x_i) = f_U(x_i) for every observed input x_i. The label rule reflects with the frame, so the fixed inputs retain their labels. For the two-dimensional example above, both covariances have determinant 2 and both give squared Mahalanobis distance 3 at x_1. Their common density is exp(-3/2)/(2 pi sqrt(2)).
The draggable frontier above uses the stylized one-spike numbers. The iid calculation extends the projection conclusion, not those particular plotted coordinates.
How many truths can the same training transcript leave unresolved?
There are two compatible endpoints. That is exactly the World + / World − ambiguity from our first picture.
Those two endpoints sweep into a full circle. The learner must now contend with a continuum of possible truths.
With d=1601 and n=2, our drawable circle is just one exact slice through a 1598-dimensional sphere of compatible truths.
Does leaving the span remove the misfitting tradeoff?
No. Under this rotational uncertainty, the training–test frontier values in the table below apply to any global linear learner, even one whose optimizer leaves the span.
| example | spike fraction revealed, a² | opposite truths' overlap | interpolator test error | best average test error | training error at that optimum |
|---|---|---|---|---|---|
| n = 1 | 0.048 | −0.904 | 0.907 | 0.196 | 246.0 |
| n = 2 | 0.092 | −0.816 | 0.826 | 0.109 | 75.6 |
Want to check every number? Open the exact coordinates and formulas.
Here X has the observed input vectors as its columns. The superscript ⊤ means transpose, so Xᵀu lists the predictor’s answers on those inputs.
Parameters: gamma = 81, d = 1601, d−1 = 1600, sqrt(gamma) = 9, sqrt(d−1) = 40.
n = 1, training-aligned 2D section:
x_1 = (41, 0)
theta_+ = (9/41, 40/41), z_+ = (40/41, -9/41)
theta_- = (9/41, -40/41), z_- = (40/41, 9/41)
x_1 = 9 theta_+ + 40 z_+
= 9 theta_- + 40 z_-
n = 2, original four-coordinate section:
x_1 = (9, 40, 0, 0), x_2 = (9, 0, 40, 0)
Adapted orthonormal basis:
s = (9, 20, 20, 0) / sqrt(881)
q = (0, 1, -1, 0) / sqrt(2)
h1 = (40, -9, -9, 0) / sqrt(1762)
h2 = (0, 0, 0, 1)
Adapted coordinates:
x_1 = (sqrt(881), 20 sqrt(2), 0, 0)
x_2 = (sqrt(881), -20 sqrt(2), 0, 0)
theta(phi) = (9/sqrt(881), 0,
sqrt(800/881) cos(phi), sqrt(800/881) sin(phi))
z_i(phi) = [x_i - 9 theta(phi)] / 40
Span-projection test-error ring:
u = P_X u + h, h in S^perp
X^T u = X^T P_X u
E_{theta}(u)
= ||u||^2 + (gamma-1)<u,theta>^2
- 2 sqrt(gamma)<u,theta> + 1
average_phi[Delta E]
= ||h||^2 [1 + (gamma-1)(1-a^2)/2]
Full compatible-sphere payoff:
theta | D = theta_0 + sqrt(1-a^2) v,
with v uniform on the unit sphere in S^perp
E[v] = 0,
E[v v^T] = (I-P_X)/(d-n)
B_D(u) = B_D(P_X u)
+ [1 + (gamma-1)(1-a^2)/(d-n)] ||h||^2
L_D(u) = L_D(P_X u)
Therefore the ambient-global-linear Bayes frontier and span frontier agree.
The same span reduction holds for worst-compatible risk.
Compatible-set dimensions:
hidden dimension = d − n
compatible sphere = S^(d-n-1)
for d = 1601 and n = 2: S^1598
Exact stylized errors:
rho = gamma n / (d−1), R = gamma rho
a^2 = rho / (1 + rho)
g_min = 1 / (1 + R)
g_interp = (d−1)(d−1+n) / (d−1 + gamma n)^2
L_at_g_min = ((gamma - 1) / (1 + R))^2
Changing the optimizer does not reveal a hidden direction. With a rotation-invariant prior over the possible worlds, the bad-training price of good linear prediction is an information problem, not merely an optimizer’s habit. Return to the Core Story’s training–test tradeoff, or see how nonlinear prediction can escape it.
LASSO can exploit advance knowledge that the signal is sparse in a known coordinate system, and then it can beat the span. The rotational model here supplies no such knowledge; the projection comparison is about what this transcript and prior justify. The contrast is reminiscent of Ng’s (2004) comparison of L1 and L2 regularization under rotations.