GATE 2025 DA – Question 22

Consider designing a linear classifier

$y = \text{sign}(f(x; w, b))$, $f(x; w, b) = w^\top x + b$

on a dataset $D = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}$, $x_i \in \mathbb{R}^d$, $y_i \in \{+1, -1\}$, $i = 1, 2, \ldots, N$. Recall that the sign function outputs $+1$ if the argument is positive, and $-1$ if the argument is non-positive. The parameters $w$ and $b$ are updated as per the following training algorithm:

$w_{new} = w_{old} + y_nx_n$, $b_{new} = b_{old} + y_n$

whenever $\text{sign}(f(x_n; w_{old}, b_{old})) \ne y_n$. In other words, whenever the classifier wrongly predicts a sample $(x_n, y_n)$ from the dataset, $w_{old}$ gets updated to $w_{new}$, and likewise $b_{old}$ gets updated to $b_{new}$. Consider the case $(x_n, +1)$, $f(x_n; w_{old}, b_{old}) < 0$. Then