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

The empirical risk isFor $g(z)={\log }_2(1+e^{-z})$,so $g$ is a convex function. Each signed margin $y_i{x}_i^T\beta$ is an affine function of $\beta$, and composition with an affine function preserves convexity. Equivalently,is a positive semidefinite matrix. Therefore $f$ is convex.

Choose $I_s$ independently and uniformly from $\{1,\dots ,n\}$. Starting from any ${\beta }_1\in C$, the projected stochastic gradient descent iteration isConditional on ${\beta }_s$, $\mathbb{E}[G_s\mid {\beta }_s]=\nabla f({\beta }_s)$, so $G_s$ is an unbiased stochastic gradient. The metric projection onto a closed convex set keeps every iterate in $C$. For a fixed step size, return the Cesaro average $\bar{\beta }=k^{-1}{\sum }_{s=1}^k{\beta }_s$.

The stochastic gradients obeyThe nonexpansiveness of metric projection and the subgradient inequality imply, after conditioning on ${\beta }_s$,Summing telescopes. Since both ${\beta }_1$ and $\hat{\beta }$ lie in the radius-$R$ set $C$, their distance is at most $2R$. By the Jensen inequality and convexity of $f$,ChooseThe two terms are then equal, and

With varying positive step sizes, the same one-step inequality isSum from $s=1$ to $k$, use $\Vert {\beta }_1-\hat{\beta }{\Vert }_2\le 2R$, and divide by $2A_1$. The Jensen inequality for the weighted average $\tilde{\beta }=A_1^{-1}{\sum }_s{\eta }_s{\beta }_s$ giveswhere $A_1={\sum }_s{\eta }_s$ and $A_2={\sum }_s{\eta }_s^2$.