The hypothesis class and margin loss are
and
Thus this is a positive semidefinite quadratic-form classifier with logistic loss. Its empirical risk, viewed as a function of the matrix parameter, is
Differentiating under the sum shows that
Hence the displayed is exactly , and the algorithm is projected gradient descent on the positive semidefinite trace ball.
The scalar factor multiplying each lies in . Since
we have the uniform gradient bound
Let parametrize the empirical minimizer . Positive semidefiniteness gives
Thus the initial distance from to is at most , while the gradient bound is .
The averaged projected-gradient bound, in its slightly looser form
applies because is convex. Choose
Substitution gives
Projection onto a positive semidefinite trace ball Created 2026-09-24 Updated 2026-11-05
Let be a real symmetric matrix with eigenpairs , and take trace radius . Its Frobenius norm projection onto the positive semidefinite trace ball is obtained by thresholding its eigenvalues. If , the projection is zero. If , it is . Otherwise and
In this last case is unique: the left side is continuous, strictly decreasing while positive, starts above at zero and reaches zero at .
To prove the reduction, use an orthonormal eigenbasis of . Replacing a feasible matrix by its diagonal part in that basis preserves nonnegative diagonal entries and the trace, hence remains positive semidefinite, while deleting off-diagonal entries decreases the squared Frobenius distance. The problem becomes projection of onto . Its multiplier equations give with the stated inactive-constraint case.
For and , the threshold gives . At radius zero the threshold itself need not be unique, although the projected matrix is; this is why that case is stated separately.