Md. Asif Uddin
I.2.X09

The subgradient at the join

gradient▲▲△

Using the perceptron loss of I.2.B07, compute the loss and a subgradient at three states: one with positive margin, one with negative margin, and one exactly at the kink. Then explain why the third case has a set of valid answers and which element the perceptron rule chooses.

Hint

At the kink, the two branches disagree about the slope. Every value between them is legitimate.

Solution

The three states. All with w\vec{w}, bb and (x,y)(\vec{x}, y) as given:

Casem=y(⟨w,x⟩+b)m = y(\langle\vec{w},\vec{x}\rangle+b)ℓ\ell∇w\nabla_{\vec{w}}∂/∂b\partial/\partial b
w=(2,1),b=0,x=(1,1),y=+1\vec{w}=(2,1), b=0, \vec{x}=(1,1), y=+1+3+300(0,0)(0, 0)00
w=(2,1),b=0,x=(−1,−1),y=+1\vec{w}=(2,1), b=0, \vec{x}=(-1,-1), y=+1−3-333(+1,+1)(+1, +1)−1-1
w=(1,−1),b=0,x=(1,1),y=+1\vec{w}=(1,-1), b=0, \vec{x}=(1,1), y=+10000(−1,−1)(-1, -1)−1-1

Case 1, m>0m > 0. ℓ=max⁡(0,−3)=0\ell = \max(0, -3) = 0, and ℓ\ell is identically zero nearby, so every derivative is zero. The rule is idle, and gradient descent agrees.

Case 2, m<0m < 0. ℓ=max⁡(0,3)=3\ell = \max(0, 3) = 3. On this branch ℓ=−y(⟨w,x⟩+b)\ell = -y(\langle\vec{w},\vec{x}\rangle+b), so ∇wℓ=−yx=−(+1)(−1,−1)=(+1,+1)\nabla_{\vec{w}}\ell = -y\vec{x} = -(+1)(-1,-1) = (+1,+1) and ∂ℓ/∂b=−y=−1\partial\ell/\partial b = -y = -1. The descent step is w←w−(+1,+1)=(1,0)\vec{w} \leftarrow \vec{w} - (+1,+1) = (1, 0), which equals w+yx=(2,1)+(−1,−1)\vec{w} + y\vec{x} = (2,1) + (-1,-1). The rule and the gradient step coincide.

Case 3, m=0m = 0. ℓ=max⁡(0,0)=0\ell = \max(0, 0) = 0, but the function is not differentiable here. Approaching from m>0m > 0 the slope is 0\vec{0}; approaching from m<0m < 0 it is −yx=(−1,−1)-y\vec{x} = (-1,-1). The subdifferential is the whole segment joining them:

∂w ℓ={ −α yx:α∈[0,1] }={ (−α,−α):α∈[0,1] }\partial_{\vec{w}}\,\ell = \{\,-\alpha\, y\vec{x} : \alpha \in [0, 1]\,\} = \{\,(-\alpha, -\alpha) : \alpha \in [0,1]\,\}

Every element is a valid subgradient, and each gives a different — equally legitimate — algorithm.

Which one the perceptron picks. α=1\alpha = 1, the most aggressive element. That is exactly what the condition “update when m≤0m \le 0” encodes: at the kink it behaves as though the example were wrong. Choosing α=0\alpha = 0 instead would give “update only when m<0m < 0”, and starting from w=0\vec{w} = \vec{0} that algorithm never takes a first step at all, because the initial margin of every example is exactly zero.

Why this matters beyond the perceptron. ReLU has precisely this structure at the origin (Chapter I.3), and every framework silently chooses a subgradient there — usually 00, occasionally 12\tfrac12 or 11. The choice is invisible in the loss curve and can change which units are dead. Knowing that a kink means a set rather than a value, and that someone has chosen for you, is worth carrying into every chapter that uses a piecewise-linear activation.

Draws on