A median can change the report card.
Split the training points into three piles and learn one predictor from each. At a training point, its own predictor may scream. The other two never saw that point: their votes can give the median a calm majority.
Medians are a familiar defense against outliers. Here, the data are clean. A training point can still be an outlier to the very predictor it helped train.
Pick a training point. Count the votes.
Each pile learns a matched filter, a span predictor: add up its training inputs’ feature vectors, each weighted by its label, then rescale. Inputs here are real numbers lifted to Fourier features, not the Core Story’s Gaussian vectors, so each predictor is linear in its feature vector without being a straight line in the scalar input. The median combines the three predictions nonlinearly. Every label is 1, so the target is the flat line at 1. Select a training point to compare the votes.
Two nearby inputs from different piles can make two predictors overshoot together. Start with Show the median’s worst training point, then try another draw to see when that defeats the median.
We use the constant target 1 to make the voting easy to see. The pile learners receive examples and feature vectors; telling them the target is constant would let them solve this example by always predicting 1.
The learned-curve experiment has not loaded. Each matched-filter pile predictor overshoots its own training points, while the other two predictions usually shield the median.
Drag sideways or enter an input to inspect between examples. Tap a training dot or use its menu for an exact point. Arrow keys on dots visit training points; the numeric input probes continuously. Vertical swipes scroll. Triangles mark values beyond the frame.
| Predictor | Whole-training MSE | Fresh-sample MSE |
|---|
The median’s scores appear in the table above.
The median’s unusually large fresh-sample gain over the mean here is helped by the Fourier map: the nuisance part of each learned predictor (everything it picked up besides the shared signal) comes in narrow peaks near that pile’s own training inputs. With Gaussian nuisance the median need not beat the mean on fresh points; its broader advantage is that it can shield the training points while keeping fresh prediction good.
Mean and median combine the same three predictors learned from the same 36 points. Only the aggregation changes. A mean of linear predictors is still linear; with equal piles, it is exactly the matched filter learned from the whole training set.
Close-up: why two calm votes shield the medianInside: a lab that moves the in-pile vote of a point from any pile, while the two piles that never saw it vote 0.9 and 1.1
The median ignores the order of its votes, so call the in-pile vote a: for any a, median(a, b, c) lies between b and c. In this separate fixed-vote illustration, the two piles that never saw the point vote b = 0.9 and c = 1.1, so however far the in-pile vote strays, the median misses the target 1 by at most 0.1, a squared error of at most 0.01. These votes illustrate the order fact; the experiment above uses its actual learned predictions.
Write the median as M and the point’s label as y (here 1). The two other-pile votes b, c give |M − y| ≤ max(|b − y|, |c − y|), so
This holds however the point was selected. For the expectation argument, fix an original sample index before drawing or sorting the data, with groups assigned independently of the data. That example is independent of each other pile’s predictor; the two errors need not be independent. Averaging over indices and training draws gives an average guarantee, not protection against every unlucky point.
Can a small ReLU network take this median?Inside: three ReLU units in two hidden layers, evaluated at the selected input
Yes. Feed the three pile predictions into just three ReLU units, arranged in two hidden layers. A ReLU keeps a positive input and replaces a negative one with zero: ReLU(t) = max(0, t).
Hidden layer 1
h1 = ReLU(a − b)
Hidden layer 2
h2 = ReLU(b − c + h1)
h3 = ReLU(c − a + h1)
Linear output
a + b − c − h2 + h3
Here a, b, and c always name piles 1, 2, and 3; the shielding illustration above instead calls whichever vote is in-pile a. The inputs also travel directly to later layers along linear skip connections. These formulas give the median for any three real predictions, including ties.
The pile predictors above learned from their own data; the combining weights here were supplied by this construction. A nonlinear network has room for this behavior.
Read every training point as a table
| Point | Pile | Input | Pile 1 | Pile 2 | Pile 3 | Median |
|---|
How are these curves learned?
A fixed Fourier feature map supplies the shared signal and nuisance.
This finite feature illustration draws 36 training inputs independently and uniformly from [0, 1), the same law as the fresh inputs, and splits them at random into three disjoint piles of 12. The target is 1. Each input has one shared signal coordinate of strength γ = 30 and 1,296 Fourier nuisance coordinates. Thus the feature count is d = 1,297, and each pile has m = 12 examples.
Each pile predictor is the matched filter: add the pile’s training inputs, each weighted by its label, and divide by γ times the sum of the squared labels: uk = Σi∈Ik yixi / (γ Σi∈Ik yi2). With every label equal to 1, that is the pile’s sum of inputs divided by 30 × 12. Besides the pile itself, the rule uses only the known signal strength.
Why the median stays accurate on training points: at a point in one pile, the other two piles’ predictions are fresh predictions, because those piles never saw that point. The median lies between them, so its squared error there is at most the sum of their two squared errors. Each pile’s expected fresh error is (d−1)/(γ2m) = 1296/(900 × 12) ≈ 0.12, so averaged over draws the median’s training and fresh errors are each at most about 0.24. The stylized paper places the inputs on an evenly spaced grid, which makes the nuisance vectors exactly orthogonal and the median’s training error exactly zero. Independent draws trade that exact zero for a small average.
Does shielding training points also protect against adversarial perturbations?
Not automatically. This median avoids the training-loss obstruction, but this estimator still inherits its linear constituents’ sensitivity to a Euclidean nuisance perturbation of RMS size δ per coordinate. The adversarial example in the stylized model shows the same budget: ‖Δ‖₂ ≤ δ√(d−1), with the signal coordinate fixed.
Why does this escape the linear training-loss obstruction?
For the single-spike iid Gaussian model with noiseless labels, consider n examples, d features and signal variance γ in the regime (d−1)/γ² ≪ n ≪ (d−1)/γ. This is the Gaussian counterpart of the Fourier illustration above.
With probability tending to 1 over the training draw, every span predictor within a fixed factor of the best test error…
Etest ≲ (d−1)/(γ2n)
…has training error at least
Ltrain ≳ (d−1)2/(γ2n2)
Split n = 3m into three fixed groups of m > 2 before observing the data. Each matched filter learns from one third of the examples, so accurate other-pile votes still need enough data. It uses the supplied γ.
E[Etest] = O((d−1)/(γ²n))
E[Ltrain] = O((d−1)/(γ²n))
The median’s two expectations, taken over training draws, are each at most 2(d−1)/(γ²(m−2)). Thus average training error and fresh-test error vanish in probability. The guarantee concerns these average errors, rather than the worst training point.
Each training point can get its answer from the two predictors that never saw it: whatever its own predictor says, the median lies between their two votes, so it misses the target by no more than the worse of them. That is how the median escapes the linear training-loss obstruction. A nonlinear model can represent this combining rule internally, too: three ReLU units suffice.