Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 4 / 30K (Mathematics of Machine Learning)

The subdifferential isIf $0\in \partial f(\alpha )$, this inequality says $f(\beta )\ge f(\alpha )$, so $\alpha$ minimizes $f$. Conversely, the zero vector satisfies the subgradient inequality at any global minimizer.

For a convex surrogate margin loss $\varphi$, the empirical risk isIt replaces the discontinuous classification error by a convex penalty on signed margins.

The matrixis the orthogonal projection onto the row space of $X$. Since $XP\beta =X\beta$, the empirical risks of $h_{\beta }$ and $h_{P\beta }$ are equal. Orthogonality givesso $q(\beta )\ge q(P\beta )$, with strict inequality unless $(I-P)\beta =0$. Therefore the minimizer lies in the row space:Because $X^T$ is injective when $X{X}^T$ is invertible, minimizing over that row space is equivalent to minimizing $r(\alpha )=q(X^T\alpha )$.

For hinge loss, chooseThe subgradient optimality condition isInjectivity of $X^T$ gives $t/n=2\lambda \hat{\alpha }$. Multiplying by $X{X}^T$ and writing $k_i$ for its $i$th column yieldsIf $y_i{x}_i^T\hat{\beta }>1$, then $t_i=0$, and $t/n=2\lambda \hat{\alpha }$ implies ${\hat{\alpha }}_i=0$.