Exercise 3.10

(a) If $\eta =1$, then the SGD algorithm will update the $w$ by: $w(t+1)=w(t)-\eta \nabla <!--\; FUNCTION\; APPLICATION\; -->e_n(w)=w(t)-\nabla <!--\; FUNCTION\; APPLICATION\; -->e_n(w)$.

When $e_n(w)=\max <!--\; FUNCTION\; APPLICATION\; -->(0,-y_n{w}^T{x}_n)$, the derivative of $e_n(w)$ when $y_n{w}^T{x}_{n}0$ (when the sample is correctly classified) is zero, the derivative is $-y_n{x}_n$ when $y_n{w}^T{x}_{n}0$ (i.e. when the sample is misclassified).

Take the derivatives into the SGD update equation, we see that’s exactly PLA.

(b) For logistic regression, we have $\nabla <!--\; FUNCTION\; APPLICATION\; -->e_n(w)=\frac{-y_n{x}_n}{1+e^{y_n{w}^T{x}_n}}$. If $w$ is very large: * When $y_n{w}^T{x}_{n}0$, $\nabla <!--\; FUNCTION\; APPLICATION\; -->e_n(w)\approx 0$. * When $y_n{w}^T{x}_n\le 0$, $\nabla <!--\; FUNCTION\; APPLICATION\; -->e_n(w)\approx -y_n{x}_n$.

The above results are consistent with the values used in PLA.

This is another indication that the logistic regression weights can be used as a good approximation for classification.