GATE DA 2025 — Question 22

Consider designing a linear classifier

\(y = \mathrm{sign}\big(f(x, w, b)\big), \qquad f(x, w, b) = w^{T} x + b\)

on a dataset \(D = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\}\), with \(x_i \in \mathbb{R}^{d}\), \(y_i \in \{+1, -1\}\), \(i = 1, 2, \dots, 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_{\mathrm{new}} = w_{\mathrm{old}} + y_n x_n, \qquad b_{\mathrm{new}} = b_{\mathrm{old}} + y_n\)

whenever \(\mathrm{sign}\big(f(x_n, w_{\mathrm{old}}, b_{\mathrm{old}})\big) \neq y_n\). In other words, whenever the classifier wrongly predicts a sample \((x_n, y_n)\) from the dataset, \(w_{\mathrm{old}}\) gets updated to \(w_{\mathrm{new}}\), and likewise \(b_{\mathrm{old}}\) gets updated to \(b_{\mathrm{new}}\).

Consider the case \((x_n, +1)\) with \(f(x_n, w_{\mathrm{old}}, b_{\mathrm{old}}) < 0\). Then