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

The candidate $\Pi$ is tacitly required to belong to $S$, as in the usual variational characterization of convex projection; this feasibility holds for the candidate constructed in part (b). Use the Frobenius inner productFor any $Z\in S$,and henceThus $\Pi$ minimizes the squared Frobenius distance over $S$. Since that objective is strictly convex,

Since $M⪰0$ but $M\notin S$, its eigenvalues satisfyThe continuous decreasing functionfalls from $q(0)>s$ to zero, so there is a unique $\rho >0$ for which $q(\rho )=s$.

PutThen $\Pi ⪰0$ and $\mathrm{Tr}\Pi ={\sum }_i{p}_i=s$, so $\Pi \in S$. Moreoverand thereforeFor any $Z\in S$,Whenever $p_i>0$, the corresponding eigenvalue of $A$ is exactly $\rho$, while terms with $p_i=0$ contribute nothing. ConsequentlyIt follows thatPart (a), equivalently the formula for projection onto a positive semidefinite trace ball, now gives

The hypothesis class and margin loss areandThus this is a positive semidefinite quadratic-form classifier with logistic loss. Its empirical risk, viewed as a function of the matrix parameter, isDifferentiating under the sum shows thatHence the displayed $g_i$ is exactly $\nabla F(M^{(i)})$, and the algorithm is projected gradient descent on the positive semidefinite trace ball.

The scalar factor multiplying each $Y_j{X}_j{X}_j^T$ lies in $[0,1]$. Sincewe have the uniform gradient boundLet $\hat{M}$ parametrize the empirical minimizer $\hat{h}$. Positive semidefiniteness givesThus the initial distance from $M^{(1)}=0$ to $\hat{M}$ is at most $D=s$, while the gradient bound is $G=C^2$.

The averaged projected-gradient bound, in its slightly looser formapplies because $F$ is convex. ChooseSubstitution gives