Price of Robustness, Interactive

← text notes · von Berg, Fono, Datres, Maskey & Kutyniok, ICLR 2026. Five widgets: what the margin and the co-margin measure, why isoperimetry makes Lipschitz functions nearly constant, the surrogate trick at the heart of every proof, the law itself as a calculator, and a toy experiment you can rerun. Everything is computed in your browser.

1. Margin, class stability and co-stability in 2-D

The data are drawn from a Gaussian blob. The "true" label is the sign of x₂, and each label is flipped with probability η, so the Bayes risk is R* = η. Pick a classifier f = sgn∘g. The page computes the margin h_f(x), the distance from x to the nearest point with the other label, on a 240 × 180 grid with an exact distance transform. It then averages h_f over 2000 fresh draws to get the class stability S(f) = E[h_f] (Definition 1). It also reports the co-stability S*(g) = E|g|, the Lipschitz constant L(g), and their ratio, the normalized co-stability S̄*(g) (Definition 10). Click the picture to drop a point and see its margin disc.

Things to try. Linear, θ = 0, b = 0 is the Bayes classifier: its S(f) ≈ 0.7 is the mean |x₂|. Now slide the scale s. S*(g) and L(g) move together and S(f) and S̄* do not budge: rescaling a score changes nothing about the classifier (the paper's point against using Lipschitz constants of g). Switch to wavy and raise k. The boundary wiggles and S(f) drops, but S̄* drops much faster, because L(g) grows like A·k. The inequality S(f) ≥ S̄*(g) (Eq 7) always holds, but it can be very loose. Finally the 1-NN memoriser fits every training label, including the flipped ones. It pays with little islands around each flipped point, and its S(f) falls. That is Corollary 6 in miniature: fitting below the noise level costs margin.

2. Isoperimetry: Lipschitz functions are nearly constant in high dimension

Draw x from N(0, I/d), so that ‖x‖ ≈ 1 whatever the dimension. This distribution is c-isoperimetric with c = 1 (Definition 3). For any L-Lipschitz f, the probability that f(x) strays t from its mean is at most 2 exp(−d t²/(2cL²)). The spread is of order L√(c/d), which shrinks with d. The left panel shows 4000 values of f(x) − Ef on a fixed axis. The right panel shows the empirical tail against the isoperimetric bound, and against Hoeffding's bound 2 exp(−t²/2), which only knows that f lies in [−1, 1] and so cannot improve with d.

Step d from 1 to 1000 with x₁ selected. The histogram narrows like 1/√d, and the green bound falls with it. With |x₁| selected you are looking at the margin of a fixed classifier. It concentrates too (Fact 2 in the proof of Theorem 4), so hardly any points sit much nearer the boundary than S(f). The last option, tanh(√d·x₁), is bounded but has Lipschitz constant √d. It never concentrates, and the isoperimetric bound is no better than Hoeffding's. This is why the paper can gain a factor √d only when the relevant Lipschitz constant (here 2/S) stays below √(d/c), that is, when S ≳ √(c/d).

3. The surrogate: trading a Lipschitz constant for a thin band

A classifier jumps, so the Lipschitz toolbox cannot touch it directly. Every proof in the paper replaces f = sgn∘g with the ramp F = sgn_γ∘g. The ramp is (L/γ)-Lipschitz, and it disagrees with f only where |g| < γ. So the error splits into two terms. The smooth part costs (1/γ)·√(c log|F| /(nd)), which is Bubeck and Sellke's bound for Lipschitz classes. The band part costs P(|g| ≤ γ), which isoperimetry makes exponentially small once γ is below the typical margin. A small γ makes the band cheap and the smooth part expensive. A large γ does the opposite. The paper takes γ = S/2.

Model for the margin: the score is t = d_f(x), whose absolute value is the margin. It is taken to be ±(S + √(c/d)·Z) with Z standard normal and c = 1: a 1-Lipschitz function fluctuating at the isoperimetric scale around its mean S. The band probability is then exact, not a bound.

The tent |sgn − sgn_γ| in the left panel is the whole trick of Section 5. sgn jumps by 2 at zero, but the tent is continuous with slope 1/γ. So a small change of the parameters moves the tent a little and cannot flip it. In the right panel, drop d until √(c/d) is comparable to S. The band term no longer vanishes at any γ, and the bound is stuck near 1. That is the 2 exp(−dS²/(8c)) term in Theorem 4 at work.

3b. Example 9: why class stability alone cannot survive a covering argument

Take g_w(x) = w·tanh(x) for x ~ N(0, 1). For every w ≠ 0 the boundary is the single point 0, so S(f) = E|x| ≈ 0.80, and w and −w are close in parameter space. Yet sgn∘g_w and sgn∘g_−w disagree everywhere.

Move w towards 0. S(f) stays at 0.80 and the normalized co-stability S*(g)/L(g) = E|tanh x| ≈ 0.56 stays fixed as well, because numerator and denominator both carry |w|. Only the unnormalized co-stability S*(g) = |w|·E|tanh x| sees the danger. That is why Theorem 13 has to assume S*(g) ≥ S* and L(g) ≤ L separately, and it is also why its covering term J·ε̃/S* cannot be expressed through the ratio alone. The notes return to this under "Questions and doubts".

4. The law of robustness as a calculator

Corollary 6: with probability at least 1 − δ, every classifier in the class that fits the training set below the noise level (R̂ ≤ R* − ε) has

S(f) < S* = max{ (3K/ε)·√(c·p/(nd)) , √((8c/d)·log(6K/ε)) }, with p = log|F|.

The absolute constant K is not given in the paper, so only the shape is meaningful. Everything here is a ceiling: a memoriser can have any stability below the curve.

The left panel answers "how many parameters must a memoriser have before a margin of S is even possible?" The answer is p ≳ (εS/3K)²·nd/c. At p = n the ceiling is of order √(c/d), which is about the margin a random hyperplane gets for free (widget 2, |x₁|). The right panel fixes p (use the target S slider as the x-marker) and compares the three Rademacher bounds as functions of S. Theorem 4.2 beats the stability-free bound exactly when S > √(c/d) (App C.1). Theorem 4.1 is far weaker at p ≫ n, because the 2ⁿ subsets in its proof cost a term that does not shrink with n.

5. A toy law: interpolating random features

This is the same experiment as code/rf_margin_toy.py, at browser scale. Inputs are uniform on the unit sphere in ℝ^d. Labels are sgn(x₁) with a fraction flipped. The model is g(x) = a·relu(Wx)/√p with W frozen and Gaussian, and only a is fit. For p ≥ n that fit is the minimum-norm interpolant, for p < n least squares. For each p the page estimates S(f) on 200 fresh points, by walking to the boundary DeepFool-style and then bisecting. That gives an upper bound on each distance, like the paper's adversarial estimate.

The margin is smallest around p = n, where the interpolant is forced and ‖a‖ explodes (the double-descent peak). With more parameters, the minimum-norm solution has room to push the boundary away from the data. Two caveats, both in the notes. First, small non-interpolating models (p < n) can have larger margins. The law only constrains memorisers. Second, the margin plateaus rather than climbing towards the ceiling, because frozen random features converge to a fixed kernel interpolant. Overparameterization is necessary for stability, not sufficient.