Md. Asif Uddin
Problem I.2.B05

What happens to the bound as the margin closes

limit▲▲△

Counts are exact; ratios to 4 d.p.

STATEMENT

Analyse the mistake bound (R/γ)2(R/\gamma)^2 as γ→0+\gamma \to 0^{+} at fixed RR. Tabulate it, state the limit, and say precisely what the theorem still guarantees for near-separable data — and what it stops guaranteeing.

GIVEN

Novikoff’s bound k≤(R/γ)2k \le (R/\gamma)^2 from I.2.B03, with the radius fixed at R=1R = 1 and the geometric margin γ\gamma shrinking.

FIND

The bound at γ∈{0.5, 0.1, 0.01, 10−3, 10−6}\gamma \in \{0.5,\ 0.1,\ 0.01,\ 10^{-3},\ 10^{-6}\}; the limit as γ→0+\gamma \to 0^{+}; and the status of the guarantee at γ=0\gamma = 0 exactly.

STRATEGY

Evaluate, then take the limit, then separate two cases that look continuous but are not: γ\gamma small and γ\gamma zero.

SOLUTION

Step 1 — tabulate. With R=1R = 1 the bound is simply γ−2\gamma^{-2}.

γ\gamma(R/γ)2(R/\gamma)^2
0.50.544
0.10.1100100
0.010.0110,00010{,}000
10−310^{-3}10610^{6}
10−610^{-6}101210^{12}

Step 2 — the rate. The bound is quadratic in 1/γ1/\gamma, so halving the margin quadruples the work:

(R/(γ/2))2(R/γ)2=4\frac{(R/(\gamma/2))^2}{(R/\gamma)^2} = 4

This is worth stating as a rule of thumb, because it is the reason near-separable problems are qualitatively different from comfortably separable ones rather than merely slower.

Step 3 — the limit.

lim⁡γ→0+(Rγ)2=+∞\lim_{\gamma \to 0^{+}} \left(\frac{R}{\gamma}\right)^{2} = +\infty

Step 4 — the two cases, which are not the same.

Case γ>0\gamma > 0, however small. The data is separable. The theorem applies and the algorithm does terminate, in finitely many updates. The guarantee is intact — it has merely become useless in practice, because a finite number can exceed any budget anyone has.

Case γ=0\gamma = 0 exactly. There is no separating u\vec{u} with positive margin. Step 1 of the proof in I.2.B03 has no lower bound to offer, the squeeze never closes, and the conclusion is not weakened but withdrawn. The algorithm does not terminate at all.

The distinction matters because the two cases are indistinguishable from outside. A run that has made 10610^6 updates might be at γ=10−3\gamma = 10^{-3} and one update from finishing, or at γ=0\gamma = 0 and never finishing. The perceptron has no test that separates them, and no amount of patience resolves it.

Answer

lim⁡γ→0+(Rγ)2=+∞,quadratically: halving γ quadruples the bound.\lim_{\gamma \to 0^{+}} \left(\frac{R}{\gamma}\right)^{2} = +\infty, \qquad \text{quadratically: halving } \gamma \text{ quadruples the bound.}

For every γ>0\gamma > 0 the guarantee holds and termination is certain. At γ=0\gamma = 0 the guarantee does not degrade — it disappears, and so does termination.

Check — sanity

The tabulated values satisfy the quadratic rule. From γ=0.1\gamma = 0.1 to γ=0.01\gamma = 0.01 the margin fell by 10×10\times and the bound rose by 100×100\times, as γ−2\gamma^{-2} requires.

The bound is scale-invariant in the right way. Doubling every coordinate doubles both RR and γ\gamma, leaving R/γR/\gamma — and therefore the bound — unchanged. A mistake count must not depend on the units the data is measured in, and it does not.

It matches the worked run. I.2.B02 had R=2R = 2, γ=0.4472\gamma = 0.4472, bound 2020, actual 22. Consistent.

Where this breaks

The whole analysis holds RR fixed while γ\gamma moves. In real data they move together: adding a distant outlier raises RR and usually lowers γ\gamma, so the bound degrades on both factors at once and the quadratic rate above is an underestimate of the damage. The single-variable limit is a clean statement about the formula, not a forecast about a dataset.

Variation

Fix γ=0.1\gamma = 0.1 and let R→∞R \to \infty instead. Compare the rate of blow-up with the γ→0\gamma \to 0 case, and say which of the two a practitioner can actually control.

Draws on