SYDE 572 SVM Grad

Q2

For the first term, $|w|$, provided that this is the L2 norm, we have:

$${\nabla }_w(|w|)=\frac{w}{|w|}$$

For the second term (hinge loss), we need to partition the domain based on whether the term inside the $\max$ function is positive or not:

1. If $1-c_i\cdot h(x_i|w,w_0)\le 0$, then the data point is correctly classified. The $\max$ function returns $0$, and the gradient is $0$.
2. If $1-c_i\cdot h(x_i|w,w_0)>0$, then the hinge loss affects the gradient, returning $1-c_i\cdot h(x_i|w,w_0)$. We need to calculate the gradient of this term.

The gradient of $1-c_i\cdot h(x_i|w,w_0)$ with respect to $w/w_0$ is:

$${\nabla }_w(1-c_i\cdot h(x_i|w,w_0))=-c_i\cdot {\nabla }_w(h(x_i|w,w_0))$$

Assuming $h(x_i|w,w_0)$ is a linear function, such as $h(x_i|w,w_0)=w^T\cdot x_i+w_0$, the gradient of $h(x_i|w,w_0)$ with respect to $w_0$ is:

$$\nabla (h(x_i|w,w_0))=x_i$$

Combining the two steps above, the gradient of hinge loss for case 2 is just $-c_i\cdot x_i$.

Combining the two cases, we can write the gradient of the 2nd term as:

$$\frac{\beta }{N}\cdot \sum (-c_i\cdot x_i)\cdot I(1-c_i\cdot h(x_i|w,w_0)>0)$$

where $I[\cdot ]$ is an indicator function that returns $1$ if the condition inside the brackets is true, and returns $0$ otherwise.

Combining everything, we have:

$${\nabla }_w\left(L_{\text{soft margin}}\left(\left[\frac{w}{w_0}\right]\right)\right)=\frac{w}{|w|}+\frac{\beta }{N}\cdot \sum (-c_i\cdot x_i)\cdot I(1-c_i\cdot h(x_i|w,w_0)>0)$$

Q3

The given formula provides a numerical approximation of the partial derivative using the definition of partial derivative as the limit of the slope of the tangent line. It calculates the difference in the value of $L$ when $w_i^{\prime }$ is slightly perturbed by $h$, divided by $h$.

To calculate this approximation for each dimension of the 1000-dimensional weight vector $w$, we need to:

1. Evaluate $L$ once with the original weight vector $(w_1^{\prime },w_2^{\prime },\dots ,w_{1000}^{\prime })$
2. For each dimension $i$ from $1$ to $1000$:
   1. Create a perturbed weight vector by adding $h$ to $w_i^{\prime }$.
   2. Evaluate $L$ with this perturbed weight vector.

Therefore, we need:

• $1$ evaluation of $L$ with the original weight vector
• $1000$ evaluations of $L$ for each perturbed weight vector

So, we have a total of $1+1000=1001$ forward evaluations.