 Solution

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